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

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

Лента разбита на ячейки. Во всякой ячейке в точности один символ из внешнего алфавита 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.

 q0...qi...qm
...     
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 обеспечивает дописывание | в случае, когда произошла замена α на |.