Тезис Черча

Теперь мы располагаем всеми необходимыми определениями для точ-

ной формулировки понятия алгоритм. При рассмотрении алгоритма наи-

более часто речь идет о вычислении значений функций.

n- арная частичная функция f называется вычислимой, если суще-

ствует алгоритм для вычисления функции f. Тем самым это те функции,

для которых мы должны дать точное определение.

n- арная частичная функция f называется рекурсивной, если суще-

ствует машина Тьюринга вычисляющая функцию f. Тем самым это те

функции, для которых существует точное определение, которое разъяс-

нено выше.

При этом ясно, что каждая рекурсивна функция вычислима.

Точным определением понятия алгоритма является следующее поло-

жение, выдвинутое Алонзо Черчем в 1936 г.

Тезис Черча. Каждая вычислимая функция рекурсивна.

Сможем ли мы доказать тезис Черча? Нет, т.к. у нас нет точного

определения вычислимости. Это положение является соглашением, воз-

никшим в результате длительного исследования интуитивного понятия

алгоритма. Показана рекурсивность огромного количества вычислимых

функций. Никто не сумел построить вычислимую функцию, рекурсив-

ность которой нельзя было бы доказать, или хотя бы указать правдопо-

добный метод построения такой функции. Тезис Черча—естественнона-

учный факт, подтвержденный опытом, накопленным математикой за весь

период ее развития.

Алгоритмически неразрешимые проблемы

Разработка точного определения алгоритма позволила получить стро-

гое доказательство несуществования алгоритма в ряде известных мате-

матических задач.

Десятая проблема Гильберта

Рассмотрим уравнение

f(x1, x2, . . ., xn) = 0,

где f(x1, x2, . . ., xn) — многочлен от n нескольких переменных с целы-

ми коэффициентами. Такие уравнения называются диофантовыми в честь

греческого математика Диофанта.

Простейшее из таких уравнений ax + by = c имеет хорошо известный

в теории чисел алгоритм для нахождения решений.

В августе 1900 г. в Париже состоялся II Международный конгресс

математиков, на котором Д.Гильберт прочитал доклад «Математиче-

ские проблемы». Среди 23 проблем, поставленных Д.Гильбертом, деся-

тая проблема может быть сформулирована в следующем виде.

Отыскать алгоритм для распознавания по произвольному диофанто-

вому уравнению разрешимо ли это уравнение в целых числах.

Разумеется в то время речь шла лишь о положительном решении деся-

той проблемы Гильберта - об «указании способа». То, что «способ реше-

ния» может отсутствовать - мысль о такой возможности в 1900 г. никому

не приходила в голову. Лишь в 30-х гг. оформилось математически точное

понятие алгоритма. К концу 40-х гг. вера в адекватность математически

точного понятия алгоритма укоренилась уже настолько, что можно было

серьезно ставить вопрос об отрицательном решении десятой проблемы

Гильберта и других классических проблем, касающихся существования

алгоритмов. В начале 50 годов появились работы, направленные на до-

казательство несуществования такого алгоритма.

В 1970 году Ю.Матиясевич завершил доказательство алгоритмиче-

ской неразрешимости десятой проблемы Гильберта.

Понятие алгоритма появляется не только тогда, когда речь идет о вы-

числении значений функций. Разрешающим методом для формальной си-

стемы F называется такой метод, с помощью которого для любой данной

формулы A из F мы можем за конечное число шагов решить, будет ли A

теоремой системы F или нет. Проблема разрешимости состоит в следую-

щем: найти такой метод (алгоритм) или доказать, что его не существует.

63

Можно сформулировать еще более общую проблему, чем проблема

разрешимости для формальных систем. Предположим, что B —подмно-

жество множества A. Разрешающим методом для B в A называется та-

кой метод, с помощью которого для каждого элемента x из A мы можем

за конечное число шагов решить, принадлежит x множеству B или нет.

В десятой проблеме Д.Гильберта в качестве A выступают все диофан-

товы уравнения, а в качестве B диофантовом уравнения, разрешимые в

целых числах.