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

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

Каждая машина Тьюринга имеет три алфавита: внешний А, внутренний 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 Универсальная машина Тьюринга существует.

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

Дата добавления: 2014-01-13