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

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

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

Пусть 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. Если она не остановилась, то процесс повторяется. За конечное число шагов функционирование построенной машины Тьюринга завершится.