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

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

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