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

Универсальный алфавит; универсальная кодировка

Каждая машина Тьюринга имеет три алфавита: внешний А, внутренний Q и алфавит сдвигов S. Все три алфавита - конечные множества, и можно считать, что

.

Тогда любое слово над однозначно разбивается на слоги (подслова) (возможно, и однобуквенные) над алфавитами A, Q, S. В частности, любую клетку программы машины как отображения можно закодировать как пятибуквенное слово над , задающее соответствие . Если условиться, что программа выписывается последовательно по столбцам сверху вниз, то мы получим стандартную запись программы в виде «длинного» слова над алфавитом . Поставим следующий вопрос: «Нельзя ли выбрать достаточно простой алфавит, с помощью слов которого можно будет кодировать все буквы, а значит, и слова над (т.е. внешние слова и программу машины)?» Оказывается, в качестве такого простого алфавита, называемого универсальным, можно взять двухбуквенный алфавит {0; 1}. Опишем стандартную кодировку букв алфавита словами над {0; 1} с помощью таблицы кодирования (см. табл. 15.6).

Кодировка с помощью этой таблицы называется стандартной. (Ясно, что стандартная кодировка допускает однозначное декодирование дли любых A, Q, S. Поэтому можно считать, что всегда применяется кодировка с помощью {0; 1} и что все машины работают со словами над алфавитом {0; 1}.

Таблица 15.6.

Буква	Код (слово) над {0; 1}
Сдвиги	-1
+1
Буквы	Λ
…	…
…	…
Состояния
…	…
…	…

Определение 15.12.Машина Тьюринга Т называется самоприменимой, если она применима к слову и_Т стандартной записи на ленте своей программы.

Это определение разбило все множество машин Тьюринга МТна два класса: MT_S - класс самоприменимых и MT_пS - класс несамоприменимых машин.

Сформулируем проблему распознавания самоприменимости: «Существует ли такая машина Тьюринга S, которая умеет распознавать самоприменимость, т. е. по слову и_Т, кодирующему программу машины Т, сообщать, является ли машина Т самоприменимой или нет?» Оказывается, имеет место следующая теорема.

Теорема 15.10.Проблема распознавания самоприменимости является алгоритмически неразрешимой по Тьюрингу проблемой.

Допустим противное, т. е. что существует машина S, решающая проблему самоприменимости, причем

S (и_Т)= 1, если Т - самоприменима,

S (и_Т)= 0, если Т - несамоприменима.

Если машина S существует, то ее можно перестроить в машину , которая в случае, когда и_Т - кодировка программы несамоприменимой машины, перерабатывает и_Т в слово «0» и останавливается, а в случае, когда и_Т - кодировка программы самоприменимой машины, «вы­печатывает», уходя вправо, бесконечный хвост «1». Покажем, что существование машины , а значит и S, ведет к противоречиям. Для этого применим к слову . Возможны два исхода:

а) после применения к машина напечатает 0 и остановится, но, с одной стороны, это означает (0) - несамоприменимость, а с другой (остановка машины) - самоприменимость;

б) в результате применения к идет без остановки печать бесконечного хвоста единиц. Хвост единиц означает теперь самоприменимость, а это противоречит тому, что машина не останавливается.

Полученное противоречие и доказывает теорему.

В заключение опишем, что такое универсальная машина Тьюринга. В обычной машине Тьюринга программа «зашита» в устройство управления, а входная информации (условия задачи) записывается на бесконечной ленте. В универсальной машине в устройстве управления записана программа, реализующая алгоритм подражания, т. е. программную реализацию правил работы любой машины (см. п.15.2), вернее, правила обращения с ее программой. Тогда входной информацией для универсальной машины является па­ра - слово и_т, стандартно кодирующее машину-алгоритм, решающий данный класс задач Z; и слово v_z, кодирующее условие задачи . Универсальная машина, используя и_т, перерабатывает v_z в T(v_z).

Ясно, что для построения универсальной машины потребуется использование техники машин с полулентами и универсального алфавита. Эта машина будет работать очень «вяло», теряя очень много времени на переходы от обрабатываемого слова к программе и обратно, однако ясно, что справедлива следующая теорема.

Теорема 15.11Универсальная машина Тьюринга существует.

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