Универсальная машина Тьюринга

Систему команд машины Тьюринга можно интерпретировать и как описание работы конкретного механизма, и как программу, управляющей работой механизма МТ. Обе интерпретации используют на практике. Для современного инженера это обстоятельство вполне естественно. Он хорошо знает, что любой алгоритм управления может быть реализован либо аппаратурно – построением соответствующей схемы, либо программно – написанием программы для универсальной управляющей ЭВМ. В одном случае МТ «запаивается» в электронную схему (часто такой подход применяется в военной технике). Во втором случае мы имеем дело с привычной практикой – разработки приложений на ЭВМ.

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

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

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

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

Любую МТ U, обладающую указанными свойствами называют универсальной машиной Тьюринга.

Лекция 3

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