Эмулятор машины Тьюринга

Как пользоваться эмулятором

• Введите алфавит для МТ (символ λ вводить не нужно) и нажмите кнопку "Задать"
• Введите слово на ленте (через саму ленту или используя поле для ввода слова)
• Для перемещения головки на определённую ячейку, дважды кликните по ней
• Добавьте необходимое число состояний (при необходимости измените имена состояний)
• Задайте параметры переходов (символ для записи, сдвиг и новое состояние)
• Выберите начальное состояние (если оно отличается от q0)
• Нажмите кнопку "Запустить" для выполнения МТ до состояния останова или кнопку "Сделать шаг" для выполнения одного шага
• Если не получается разобраться, используйте один из нескольких подготовленных примеров

Что такое машина Тьюринга?

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

• бесконечная лента, состоящая из ячеек
• головка для считывания/записи символов на ленте
• устройство управления

Бесконечная лента

Лента в машине Тьюринга состоит из ячеек, в которые можно записывать символы из заданного алфавита, а также считывать их. Если на ленте ничего не записано, то считается, что там записан специальный символ λ. Данный символ дополняет алфавит, но не входит в него явным образом.

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

Считывающая/записывающая головка

В каждой машине Тьюринга есть специальная головка, указывающая на одну определённую ячейку на ленте. Данное устройство позволяет считывать символ с ячейки, над которой находится, или записывать символ в эту ячейку. Также головка может перемещаться влево и вправо на одну ячейку, или оставаться на месте.

Устройство управления

Под устройством управления понимается таблица состояний и правил перехода для машины Тьюринга. Состоянием называется строка таблицы, в которой в данный момент находится машина. Состояние, в котором находится машина перед запуском называется начальным, обычно обозначается именем q0. Для завершения работы МТ используется специальное терминальное состояние, которое обозначается как !.

Таблица имеет размер |Q|x|A|, где |Q| — количество состояний, а |A| — размерность алфавита (включая символ λ). В первой (заголовочной) строке написаны символы алфавита. В каждой из ячеек таблицы, относящихся к строкам с состояниями, располагаются тройки <char, action, state>, определяющие действие машины, которое она должна сделать, если находится в данном состоянии и на ленте записан символ из заголовочной ячейки данного столбца:

• char — символ, который нужно записать на ленту
• action — действие, которое нужно совершить после записи (одно из трёх действий: L — сдвиг влево, N — остаться на месте, R — сдвиг вправо)
• state — состояние, в которое необходимо перейти

Допускаются краткие записи для правил:

• Если необходимо выполнить только сдвиг, оставшись в том же состоянии, то достаточно записать только символ перемещения: L, N или R
• Если нужно выполнить останов, то достаточно записать !
• Если нужно записать пустой символ (λ), то можно поставить пробел или запятую перед символом сдвига: ,R,q0

Примеры машин Тьюринга

Пример 1 (загрузить в эмулятор). К двоичному числу прибавить 1. В начальный и конечный момент головка должна находиться на самом старшем бите слова (слева).

Q \ A	0	1	λ
q0	R	R	λ L q1
q1	1 N q2	0 L q1	1 N !
q2	L	L	λ R !

Так как изначально по условию головка МТ находится на самом старшем бите, а увеличивать надо младший, необходимо сначала переместить головку на младший бит, что выполняется в состоянии q0: как только лента увидит символ λ, она сдвинется влево (на младший бит) и перейдёт в состояние икремента (q1).

В состоянии q1 возможны следующие ситуации:

• младший бит равен 0, его нужно заменить на 1 и переместить головку на старший бит (через состояние q2)
• младший бит равен 1, его нужно заменить на 0, сдвинуться левее и остаться в этом же состоянии
• в процессе замены 1 на 0 достигнут пустой символ (было записано число из одних единиц), вместо него надо записать 1 и остановить МТ

Состояние q2 нужно лишь для выполнения условия остановки головки на старшем бите. Оно полностью аналогично начальному состоянию, только движение происходит в левюу сторону и при достижении пустого символа головка сдвигается вправо и выполняется останов.

Пример 2 (загрузить в эмулятор). В слове из алфавита {a, b} инвертировать символы. В начальный момент головка находится в начале слова.

Q \ A	a	b	λ
q0	b R q0	a R q0	!

До тех пор, пока под головкой не окажется пустой символ, вместо символа a записывается символ b, а вместо b записывается a и выполняется сдвиг головки вправо на очередной символ.