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

Краткие теоретические сведения

Машина Тьюринга (кратко — МТ) математическое понятие, введенное английским математиком А. Тьюрингом как формальное уточнение понятия алгоритма. В каждой МТ есть следующие 3 части:

• неограниченная в обе стороны лента, разделенная на ячейки;
• устройство управления (УУ);
• головка (Г).

С каждой МТ связан алфавит символов A и набор внутренних состояний Q (всего N cостояний, обозначаемых q₀, q₁, ... q_n − 1). В каждой ячейке ленты записан один символ из A (считается, что A содержит «пустой» символ Λ «лямбда», а отсутствие записи в ячейке интерпретируется как запись символа Λ). УУ может находиться в одном из состояний q₀ ... q_n − 1 (в начале работы УУ находится в состоянии q₀). В каждый момент времени головка обозревает одну из ячеек ленты.

Совокупность сведений о состоянии УУ и записи на ленте машины называется конфигурацией МТ. УУ содержит команды, совокупность которых называется программой МТ. Для каждого символа aлфавита A и каждого состояния q₀ ... q_n − 1 программа содержит в точности одну команду. Выполнение любой команды заключается в следующем:

• заменяется записанный в обозреваемой ячейке символ на новый символ;
• Г сдвигается на 1 ячейку вправо или влево (может и не сдвигаться);
• происходит переход в новое состояние.

Команда может быть:

• обычной;
• заключительной.

Каждую команду можно записать в виде триады < a | m | i >, где a — записываемый на ленту символ, m — одна из букв L (влево), R (вправо) или N (не сдвигаться), i — состояние, в которое переходит МТ (заключительное состояние обозначается знаком восклицания "!").

Работа МТ состоит из однотипных тактов. Каждый такт состоит в выполнении одной команды. Предполагается, что первоначально МТ находится в состоянии 0. Таким образом, если задать информацию на ленте и положение головки, работа МТ определяется однозначно. Работа МТ считается завершенной, если выполнилась заключительная команда. Полученное последнее cодержимое ленты является результатом работы МТ.

В эмуляторе МТ вместо обозначения пустого символа Λ используетя знак подчёркивания «_» (или «пробел» в поле «Входное слово»), а вместо названия состояния указывается только его номер.

Примеры на построение машин Тьюринга

Пример 1. К непустовму входному слову в алфавите {a, b, c} приписать справа букву «a».

       a      b      c      Λ
q0    ,R,    ,R,    ,R,   a,N,!

В начале МТ ищет правую границу входного слова, а затем пишет a в пустую ячейку и останавливается.

Пример 2. К числу, записанному в двоичной записи, добавить 1.

       0      1      Λ
q0    ,R,    ,R,    ,L,1
q1   1,N,!  0,L,   1,N,!

В начале МТ ищет правую границу входного слова, а затем переходит в состояние q₁ и идёт влево, увеличивая разряды на 1, пока не встретит 0, либо пустой символ Λ.

Пример 3. Из входного слова в алфавите {a, b, c} удалить все буквы a.

       a      b     c      Λ      #
q0    ,R,    ,R,   ,R,   #,L,1
q1    ,L,    ,L,   ,L,    ,R,2   ,L,
q2   Λ,R,   Λ,R,3 Λ,R,4   ,R,!  Λ,R,!
q3    ,R,    ,R,   ,R,   b,L,1   ,R,
q4    ,R,    ,R,   ,R,   c,L,1   ,R,

Так как МТ (в отличие от НАМ) не позволяет менять некоторую подстроку на другую произвольную подстроку, при решении подобных задач используют приём построения новой копии слова. В начале МТ ставит символ «#» в конце слова, чтобы раззграничить исходное слова от строящегося. Затем МТ циклически «переносит» по одному символу из начала входного слова в конец так, чтобы перенеслись все буквы, за исключением букв a. Таким образом, все буквы a просто стираются. По окончании работы МТ удаляет «#» и останавливается на новом слове. Команда < ,R,! > в состоянии q₂ позволяет избежать зацикливания при пустом входном слове.

Типовые задачи, решаемые студентами 110 и 111 групы на семинарах