Тезис Тьюринга-Черча и алгоритмически неразрешимые проблемы

Мы рассмотрели три математические модели для описания алгоритмов и вычисляемых ими функций, отражающие различные аспекты и представления о работе абстрактного вычислителя. Из теорем 8.1, 10.2 и 10.3 непосредственно получаем

Следствие. Классы функций, вычислимых с помощью структурированных программ, машин Тьюринга и частично рекурсивных описаний, совпадают.

Естественно, возникает вопрос о том, насколько общим является этот результат? Верно ли, что каждый алгоритм может быть задан одним из рассмотренных способов? На эти вопросы теория алгоритмов отвечает следующей гипотезой.

Тезис Тьюринга-Черча:

Всякий алгоритм может быть задан в виде соответствующей машины Тьюринга или частично рекурсивного определения, а класс вычислимых функций совпадает с классом частично рекурсивных функций и с классом функций, вычислимых на машинах Тьюринга.

Значение этого тезиса заключается в том, что он уточняет общее неформальное определения "всякого алгоритма" и "вычислимой функции" через точные формальные понятия машины Тьюринга, частично рекурсивного определения и соответствующих им классов функций. После этого можно осмысленно ставить вопрос о существовании или несуществовании алгоритма, решающего тот или иной класс задач. Теперь этот вопрос следует понимать как вопрос о существовании или несуществовании соответствующей машины Тьюринга, или (что эквивалентно) структурированной программы, или частично рекурсивного определения соответствующей функции.

Можно ли доказать этот тезис как теорему? Нет, поскольку в его формулировке речь идет о неточных понятиях "всякого алгоритма" и "вычислимой функции", которые не могут быть объектами математических рассуждений. На чем же тогда основана уверенность в справедливости тезиса Тьюринга-Черча? В первую очередь, на опыте. Все известные алгоритмы, придуманные за многие века математиками, могут быть заданы с помощью машин Тьюринга. Для всех многочисленных моделей алгоритмов, появившихся за последние 70 лет (некоторые из них мы упоминали в начале лекции), была доказана их равносильность машинам Тьюринга.
В качестве доводов в пользу тезиса Тьюринга- Черча можно также рассматривать замкнутость класса машин Тьюринга и ч.р.ф. относительно многочисленных естественных операций над алгоритмами и функциями. Отметим также, что тезис Тьюринга-Черча обращен и в будущее: он предполагает, что какие бы новые формальные определения алгоритмов ни были предложены (а таковыми, например, являются новые языки программирования), все они не выйдут из класса алгоритмов, задаваемых машинами Тьюринга.

Чтобы показать связь теории алгоритмов с "практическим" программированием, рассмотрим некоторые алгоритмичские проблемы, связанные со структурированными программами.

Зафиксируем конечный алфавит A={a0, a1,…, am-1}, включающий все символы латинского алфавита, цифры, знак пробела (пусть это будет a0), знаки ';', '=', '<', ':=' , а также знаки-ключевые слова если, то, конец, пока, делай и все. Тогда каждая структурированная программа ? представляет собой некоторое слово

в алфавите A. Не ограничивая общности, будем считать, что это слово начинается не с пробела, т.е. i1 >0. Тогда слово w? однозначно определяет натуральное число n?, m-ичной записью которого оно является, т.е.

Назовем это число номером программы ?. По тексту программы ? ее номер n? определяется однозначно. Рассмотрим теперь обратное соответствие. Конечно, не каждое число является номером некоторой структурированной программы. Поэтому сопоставим каждому числу n

N структурированную программу ?n следующим образом: если n=n? для некоторой программы ?, то ?n=?, иначе, т.е. когда n не является "естественным" номером никакой программы, сопоставим ему в качестве ?n

некоторую никогда не останавливающуюся программу P (например, программу ?5(1): x1 := x1; пока x1=x1 делай x1:=x1 все из примера 7.5).

Содержание раздела