Cтраница 4
Уже поэтому основные понятия теории вычислимости ( или, как говорят, общей теории алгоритмов) достойны внимания математиков и программистов. Но эта теория имеет и более широкий культурный аспект. [46]
Тьюринг и другие первооткрыватели теории вычислимости были первыми, кто доказал, что некоторые корректно определенные математические задачи неразрешимы, т.е. что в принципе не существует алгоритма, способного к решению всех частных случаев таких задач. [47]
Сейчас мы дадим эквивалентное определение вычислимости функции относительно а, не апеллирующее к программам с вызовом оракула. [48]
А как обстоит дело с вычислимостью. Действительно, в функцию Н могут входить физические константы - такие, как ньютоновская постоянная тяготения или скорость света, величина которых зависит от выбора единиц; или другие, описывающиеся точными числовыми выражениями - и поэтому, чтобы положительно ответить на поставленный вопрос, необходимо сначала убедиться в том, что все эти постоянные вычислимы. [49]
Теперь мы на время оторвемся от вычислимости, чтобы напомнить важнейшие факты из логики, после чего то, чему мы научились относительно вычислимости, применим к логике и, среди прочего, покажем что не существует вполне удовлетворительной универсальной механической процедуры для определения, имеет ли место логическое следование в логике первого порядка, т.е. элементарной логике. [50]
В силу тезиса Черча вопрос о вычислимости функции равносилен вопросу о ее рекурсивности. Понятие рекурсивной функции строгое. [51]
Обсуждая в общем и целом вопросы вычислимости и непредсказуемости, нам будет полезно принять более широкую, чем прежде, точку зрения на природу физических законов. Это позволит рассматривать не только схему ньютоновской механики, но и более поздние теории, пришедшие ей на смену. И сперва нам стоит окинуть беглым взглядом замечательную формулировку законов механики, предложенную Гамильтоном. [52]