Машина Тьюринга представляет собой (абстрактное) устройство, состоящее из ленты, управляющего устройства и считывающей головки.
Лента разбита на ячейки. Во всякой ячейке в точности один символ из внешнего алфавита 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=|||||.).
Решение. Рассмотрим алфавит А = {|, +, Λ}.
Машина определяется следующей программой:
| q1 | q2 | q3 | |
| | | |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={|, α, Λ}.
Программа такой машины может выглядеть так:
| q1 | q2 | q3 | |
| | | α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 обеспечивает дописывание | в случае, когда произошла замена α на |.