Словарное представление машины Тьюринга

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

Пусть V – алфавит машины Тьюринга, Q – множество её состояний, K(q) – порядковый номер соответствующий номеру состояния q.

Введём вспомогательный символ *, не входящий в алфавит V. Каждой команде вида: qa→q’a’d, сопоставим цепочку в алфавите W, который определяется . Сопоставленная цепочка будет иметь вид:*K(q)a*K(q’)a’d. Упорядоченной последовательности команд будет соответствовать последовательность цепочек в алфавите W, конкатенация этих цепочек определяет цепочку α_T. Последняя однозначно описывает машину Тьюринга T с точностью до переименованного состояния.

Следующий шаг заключается в переходе от представления в алфавите W в алфавит V.

Пусть алфавит V содержит n символов, упорядочим их произвольным образом. Алфавит W упорядочим так, чтобы символы из алфавита V имели те же номера, а дополнительные символы имели номера:

Закодировав согласно описанному ранее способу все цепочки из V^* (перенумеровав их) и все цепочки из W^*, мы можем, зная номер цепочки α_T, сопоставить ей цепочку β_T из множества V^* с тем же самым номером. Найденная цепочка будет словарным представлением машины Тьюринга в её алфавите и по этой цепочке β_T можно однозначно восстановить машину Тьюринга с точностью до наименования её состояния.

Массовые алгоритмические проблемы

Необходимо указать алгоритм, который бы определял, обладает ли предъявляемый объект из некоторого класса объектов интересующим нас свойством. Другими словами, необходимо определить, принадлежит ли рассматриваемый объект множеству M всех объектов, обладающих заданным свойством. Если существует такой частичный алгоритм, то говорят, что множество перечислимо, а поставленная массовая алгоритмическая проблема частично разрешима. Если же алгоритм всюду определён, то множество M разрешимо и поставленная проблема также разрешима.

Пусть V – алфавит, и множество M является подмножеством всех цепочек V^*. Функция F_M называется предикатом отображения:.

Частичная характеристическая функция множества M – это функция , которая определяется только для цепочек из множестваM, т.е. , .

Множество M называется разрешимым, если его характеристическая функция F_M вычислима. Множество M называется перечислимым, если его частичная характеристическая функция вычислима. Разрешённое множество M означает, что существует всегда останавливающаяся машина Тьюринга , позволяющая для любых цепочек изV^* через конечное число шагов узнать, принадлежит ли эта цепочка множеству M или нет. Перечислимость M означает, что существует машина Тьюринга , которая останавливается только в том случае, когда поданная на вход цепочка принадлежитM.

Теорема Поста:

Множество разрешимо тогда и только тогда, когда перечислимыми являются множествоM и его дополнение .

Доказательство.

Необходимость:

Если множество M разрешимо, то характеристическая функция этого множества F_M вычислима, т.е. существует машина Тьюринга , которая останавливается в обоих случаях. Частичная функцияH_M реализации машины Тьюринга из машинызацикливается в случае, когда цепочка не принадлежитM. Машина Тьюринга строится аналогично.

Достаточность:

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

Последовательно выполняются команды, сначала , потом. Если останавливается машина Тьюринга, то в качестве ответа выдаётся символ 1. Еслине останавливается, то запускается, если она остановилась, то выдаётся в качестве ответа 0. Если она не остановилась, то процесс повторяется. За конечное число шагов функционирование построенной машины Тьюрингазавершится.