Машина Тьюринга. Теорема Кука.

85. (за 4 задачи)(Теорема Кука и одноименная презентация). Рассмотреть машину Тьюринга С языком a,b,c,dmod8(трехсимвольные цепочки). Свести к КНФ.

86. Пример задания языка, для распознавания которого готовится машина Тьюринга

Пример построения машины мы проведём для более скромного языка

87. Требуемая , гдеУказания:

Переменные - переменные состояния,- переменные координаты,- переменные, описывающие в каждый момент заполнение ячеек ленты символами алфавита, где

s- состояния,

- координата,

- время

Логика назначения индексов: первым идет индекс посвящённый переменной, для - номер состояния, для- координата на ленте МТ, для- номер в алфавите,, присутствующий во всех наборах - всегда последний индекс, конкретно,

Координатные переменные

,

Переменные состояния

Алфавитные переменные для имеют средний индекс, отвечающий координате.

Пример машины Тьюринга, принимающей язык из двух слов 000 и 001:

Наиболее сложная под-коньюнкция отражает специфику машины Тьюринга

,

в том числе в тупиковых ситуациях

(тупиковая ситуация означает невыполнение Коньюнкции).

Логика этих индексов такова

Если , то для спасения ситуации переменные следующего щага должны принять те значения которые словлены правилом

т.е. машина должна перейти в состояние в момент,,

координата должна сместиться на величину :(в некотором смысле «»).

На ленте должен появиться символ :.

Остальные формулы базируются на конструкции типа

:

Например

или

- что означает одно единственное значение истины для одного и только одного из всего набора в первой скобке.

Действительно, за счет первой скобки

За счёт ,

Например, единственность координаты считывающей головки машины Тьюринга обеспечивает конъюнкция :

Например, за единственность координатной переменной в первый момент отвечает блок объединённых в под-Конъюнкцию дизъюнктов, находящихся во второй строке

.

и- аналогично,

,

- контролирует неизменность символа в отсутствии Каретки,

- переход в принимающее состояние на момент завершения работы.