1.2.3. Тезис Тьюринга

Определение 5. Функция является вычислимой, если существует такая машина Тьюринга T, что если на вход ей подать представленный в некоторой кодировке x, то

1. если функция f определена на x, и f(x) = y, то машина T останавливается на входе x, и на выходе у нее записано y;

2. если функция f не определена на x, то машина T зацикливается (не останавливается за любое конечное число шагов) на входе x.

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

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

Таким образом, если мы принимаем этот тезис, то можем смело говорить о вычислимости, не указывая конкретную модель Сразу возникает вопрос: любую ли функцию y = f(x), можно вычислить на МТ?

Ответ на этот вопрос утвердительный. Существует проблема остановки алгоритма. В общих чертах она сводится к вопросу существует ли алгоритм , который для произвольного алгоритма A и данных определял бы приведет ли работа алгоритма A к результату или нет, т.е. , если результативен и в противном случае.

Эту задачу можно сформулировать, как задачу о существовании МТ , которая для произвольной машины Тьюринга T и входного слова МТ T , если машина Тьюринга останавливается (вычислима), и , если не останавливается (не вычислима).

Теорема 1. Не существует машины Тьюринга , решающей проблему остановки для произвольной машины Тьюринга T.

Полное доказательство теоремы будет приведено в курсе лекций «Математическая логика и теория алгоритмов» здесь же приведем некоторые неформальные соображения.

Пусть существует машины Тьюринга , решающая проблему остановки для произвольной машины Тьюринга T. Однако она не способна решить эту проблему для самой себя. Следовательно необходимо построить МТ , которая решала бы проблему остановки МТ . Нетрудно представить, что потребуется построить бесконечную последовательность МТ для решения проблемы остановки, что практически невозможно сделать.

Приведем примеры некоторых неразрешимых проблем (вычислимости функции).

1. Проблема остановки машины Тьюринга на пустом слове неразрешима.

2. Нет алгоритма, который для заданной машины Тьюринга T и ее состояния qk выясняет: попадет ли машина в это состояние хотя бы для одного входного слова x .

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

Лекция 4