Машина Тьюринга

Машина Тьюринга представляет собой (абстрактное) устройство, состоящее из ленты, управляющего устройства и считывающей головки.

Лента разбита на ячейки. Во всякой ячейке в точности один символ из внешнего алфавита A={a0,a1…an}. Некоторый символ (будем обозначать его Λ) алфавита A называется пустым, а любая ячейка, содержащая в данный момент пустой символ, называется пустой ячейкой (в этот момент). Лента предполагается потенциально неограниченной в обе стороны.

Управляющее устройство в каждый момент времени находится в некотором состоянии qj, принадлежащем множеству Q={q0,q1…qm} (m=l). Множество Q называется внутренним алфавитом. Одно из таких состояний (обычно q0) называется заключительным, а некоторое другое (обычно q1) -начальным.

Считывающая головка перемещается вдоль ленты так, что в каждый момент времени она обозревает ровно одну ячейку ленты. Головка может считывать содержимое обозреваемой ячейки и записывать в нее вместо обозреваемого символа некоторый новый символ из внешнего алфавита A (возможно тот же самый).

В процессе работы управляющее устройство в зависимости от состояния, в котором оно находится и символа, обозреваемого головкой, изменяет свое внутреннее состояние q. Затем выдает головке приказ напечатать в обозреваемой ячейке определенный символ из внешнего алфавита A, а потом приказывает головке либо остаться на месте, либо сдвинуться на одну ячейку вправо, либо сдвинуться на одну ячейку влево. Попав в заключительное состояние, машина прекращает работу.

Конфигурацией на ленте (или машинным словом) называется совокупность, образованная:

1) последовательностью ai(1),ai(2)…ai(s) символов из внешнего алфавита А, записанных в ячейках ленты, где ai(1) — символ записанный в первой ячейке слева и т.д. (любая такая последовательность называется словом)

2) состоянием внутренней памяти qr

3) номером k воспринимаемой ячейки

Конфигурацию машины будем записывать так:

ai(1),ai(2)…ai(r-1)(ai(r)/qr)ai(r+1),ai(r+2)…ai(s)

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

Если машина, находясь во внутреннем состоянии qi, воспринимает ячейку с символом au, записывает к следующему моменту времени в эту ячейку символ ar, переходит во внутреннее состояние qs и сдвигается по ленте, то говорят, что машина выполняет команду qiau→qsarS, где символ S может принять одно из значений: -1 — сдвиг головки влево; +1 — сдвиг головки вправо; 0 — головка остается на месте. Список всех команд (пятерок), определяющих работу машины Тьюринга, называется программой этой машины. Программу машины часто задают в виде таблицы. Так для описанной выше ситуации в таблице на пересечении строки ai и столбца qi будет стоять qsarS.

 q0qiqm
     
au  qsarS  
     

Если в программе машины для пары (qi,au) пятерка отсутствует, то в таблице на пересечении строки au, и столбца qi ставится прочерк.

Итак, машина Тьюринга есть, по определению, набор М=(А,Q,П), где А — внешний алфавит, Q — алфавит внутренних состояний, П — программа.

Если машина, начав работу с некоторым словом P, записанным на ленте, придет в заключительное состояние, то она называется применимой к этому слову. Результатом ее работы считается слово, записанное на ленте в заключительном состоянии. В противном случае, машина называется не применимой к слову Р.

Пример. Построим машину Тьюринга, складывающую натуральные числа, записанные в унарной системе счисления (т.е. записанные при помощи одного символа |. Например 5=|||||.).

Решение. Рассмотрим алфавит А = {|, +, Λ}.

Машина определяется следующей программой:

 q1q2q3
||q1+1Λq3-1|q3-1
+|q1+1  
ΛΛq2-1 Λq0+1

Выпишем последовательно возникающие при работе этой машины конфигурации на исходном слове ||+|||, т.е. 2+3. Здесь при записи конфигурации будем использовать следующее соглашение: состояние, в котором находится машина, записывается в круглых скобках справа за обозреваемой буквой.

0) …Λ|(q1)|+|||Λ…

1) …Λ||(q1)+|||Λ…

2) …Λ||+(q1)|||Λ…

3) …Λ||||(q1)||Λ…

4) …Λ|||||(q1)|Λ…

5) …Λ||||||(q1)Λ…

6) …Λ||||||Λ(q1)…

7) …Λ||||||(q2)Λ…

8) …Λ||||||(q3)Λ…

9) …Λ||||(q3)|Λ…

10) …Λ|||(q3)||Λ…

11) …Λ||(q3)|||Λ…

12) …Λ|(q3)||||Λ…

13) …Λ(q3)|||||Λ…

14) …Λ|(q0)||||Λ…

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

Решение. Искомую машину построим в алфавите A={|, α, Λ}.

Программа такой машины может выглядеть так:

 q1q2q3
|αq1+1|q2-1|q3+1
α |q3+1 
ΛΛq2-1Λq0+1|q2-1

Применим полученную машину к слову ||.

0) …Λ|(q1)|+…

1) …Λα|(q1)Λ…

2) …ΛααΛ(q1)…

3) …Λαα(q2)Λ…

4) …Λα|Λ(q3)…

5) …Λα|(q2)|Λ…

6) …Λα|(q2)|Λ…

7) …Λα(q2)||Λ…

8) …Λ|(q3)||Λ…

9) …Λ|(q2)|||Λ…

10) …Λ|(q2)|||Λ…

11) …Λ(q2)||||Λ…

12) …Λ|(q0)|||Λ…

Введение новой буквы α и замена исходных | на α позволяет различить исходные | и новые (приписанные) |. Состояние q1 обеспечивает замену | на α, состояние q2 обеспечивает поиск α, предназначенных для замены на |, и останов машины в случае, когда α не обнаружено, q3 обеспечивает дописывание | в случае, когда произошла замена α на |.