Введение в схемы, автоматы и алгоритмы



             

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


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

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

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

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

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

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

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


Содержание  Назад  Вперед