3.2.1. Описание машины Тьюринга

Математическая модель машины Тьюринга имеет вид:

Т = < v_t; Q; W; ; ;  >,

где: VT = {ai; a2; ... an}	– множество символов внешнего алфавита;
Q = {qi; q2; ... qm}	– множество символов внутреннего алфавита;
W = {R; L; S}	– множество символов алфавита перемещения головки;
: Q  vt => vt	– функция выхода машины Тьюринга;
: Q  vt => vt	– функция переходов машины Тьюринга.
: Q  vt => vt	– функция перемещения головки машины Тьюринга.

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

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

K =  q_i , где  – слово, расположенное слева от головки;

 – слово, расположенное вправо от головки;

q_i – текущее состояние машины Тьюринга.

Введенное понятие «состояние» машины Тьюринга определяет ее «память», т. е. учет всех тех конфигураций, которые привели машину в текущее q_i состояние. Следует обратить внимание, что символ, находящийся в ячейке под считывающей головкой, является первым символом слова , т.е. =(a_j ).

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

Для удобства анализа вычислительных алгоритмов рекурсивных функций математик Пост предложил ограничить множество символов внешнего алфавита v_t двумя символами, т.е. v_t = {|; #}, где "|" (палочка) есть символ унарного кода числа, а "#" – символ пробела между числами. При этом любое целое неотрицательное число может быть представлено на информационной ленте последовательностью палочек, как это представлено в табл. 2.

Запись числа «x» эквивалентно « | ^{x + 1}».

Таблица 2

Число в десятичной системе счисления	«Слово» в унарном коде на информационной ленте
0	|
1	||
2	|||
3	||||
........................	..........................................
i

Для упорядочения составления протоколов машины Тьюринга информационную ленту ограничивают полулентой бесконечной длины только в одну сторону. Алгоритмы допустимо исследовать на левой полуленте бесконечной в левую сторону и правой полуленте бесконечной в правую сторону. В зависимости от используемой полуленты приняты различные схемы записи стандартных конфигураций машины Тьюринга (табл. 3).

Таблица 3

Стандартная	Информационная полулента
конфигурация	правая	левая
Началь-ная	qí | x 1+ 1# | x 2+ 1 # ... #| x n+ 1	| x 1+ 1# | x 2+ 1 # ... #| x n qí |
Конечная	qk | y + 1	| y qk |

Работу машины Тьюринга удобно представлять протоколом, таблицей и графом.

При протокольной записи все команды должны быть записаны упорядоченным списком. Например,

1) a_i q_í a_jq_iW

2) a_k q_i  a_i q_j W

.................................

n) a_m q_|  a_n q_k S.

При табличном представлении строки описывают текущее состояние машины, а столбцы – содержимое обозреваемой ячейки. Тогда элементами матрицы этой таблицы являются правые части команд (a_iq_jW) для соответствующей пары текущего состояния машины (а_кq_i). Табличная форма описания машины более компактна и позволяет применить матричные методы анализа для оптимизации структуры алгоритма (табл. 4).

Таблица 4

Текущее	Символы vt
состояние	аi	ак	...	am
q1	ajqiW	...
qi	...	aiqjW		...
...	...	...	...	...
q0	...	...	...	anqkS