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

Машина Тьюринга – абстрактная машина, обрабатывающая слова в произвольном внешнем алфавите А={а₀, а₁, …, a_n}. Внешний алфавит для каждой задачи выбирается свой, но один символ присутствует в любом алфавите – это пустой символ («пробел»), а₀= «_».

Устройство машины Тьюринга

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

Вдоль ленты движется каретка (считывающая и записывающая головка).

Каретка может передвигаться вдоль ленты влево и вправо. Когда она неподвижна, она стоит против ровно одной ячейки ленты; говорят, что каретка обозревает эту ячейку. А такая ячейка называется текущей или обозреваемой.

В каждый конкретный момент времени машина находится в одном из внутренних состояний и обозревает ровно одну ячейку. Множество всех внутренних состояний образует алфавит внутренних состояний машины Тьюринга Q={q₀, q₁, …,q_m}. Состояние q₁ – начальное состояние, а состояние q₀ – конечное состояние; присутствуют в любой машине Тьюринга. В начальном и конечном состояниях каретка находится над крайним левым значащим символом.

Команды машины Тьюринга

Формат команды: a_i q_j → a_i΄ K q_j΄, где

a_i, a_i΄ – символы внешнего алфавита А,

q_j, q_j΄– символы алфавита внутренних состояний Q,

K – команда сдвига каретки: L – сдвиг каретки влево, R – сдвиг каретки вправо, E – отсутствие сдвига каретки.

Последовательность команд – программа машины Тьюринга.

Порядок работы машины Тьюринга

Работа машины Тьюринга состоит из тактов. На каждом такте выполняется одна команда машины Тьюринга. Выбор команды определяется обозреваемым символом и тем внутренним состоянием, в котором находится машина в данный момент времени. Таким образом, если обозревается символ a_i и машина находится во внутреннем состоянии q_j, то машина выполняет команду a_i q_j → a_i΄ K q_j΄, в ходе чего выполняются следующие действия:

1) символ a_i в обозреваемой ячейке заменяется на символ a_i΄;

2) каретка сдвигается в соответствии с командой К;

3) машина переводится во внутреннее состояние q_j΄;

После выполнения команды происходит переход к следующему такту.

Действия машины прекращаются после выполнения команды останова.

Команда останова – это команда вида a_i q_j → a_i Е q_j, т. е. команда, которая не меняет обозреваемого символа, не сдвигает каретку, не меняет внутреннего состояния машины.

Все команды останова содержатся в заключительном состоянии q₀.

Если в ходе выполнения программы машина дойдет до выполнения команды останова, то программа в этом случае считается выполненной, и машина является применимой к входному слову.

Если в ходе выполнения программы машина не дойдет до выполнения ни одной из команд останова, то выполнение программы при этом никогда не прекращается, машина никогда не останавливается – процесс работы машины происходит бесконечно. В этом случае говорят, что машина не применима к входному слову.

Программу машины Тьюринга удобно отображать в виде таблицы. Например, команда a_i q_j → a_i΄ K q_j΄ будет отображаться следующим образом:

А Q	q0	q1	…	qj	…	qm
a0
a1
…
ai				ai΄ K qj΄
…
an

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

Внешний алфавит: А={_,0,1,2,3,4,5,6,7,8,9}.

Пример начальной конфигурации:

Заключительная конфигурация:

Для решения задачи будем в цикле вычитать единицу из второго числа и прибавлять единицу к первому до тех пор, пока не закончится второе число.

А Q	q0	q1	q2	q3	q4	q5	q6	q7	q8
_	_Eq0	_Rq2	_Lq3	_Rq6	_Lq5	1Rq1	_Lq7	_Lq7	_Rq0
0	0Eq0	0Rq1	0Rq2	9Lq3	0Lq4	1Rq1		0Lq8	0Lq8
1	1Eq0	1Rq1	1Rq2	0Lq4	1Lq4	2Rq1		1Lq8	1Lq8
2	2Eq0	2Rq1	2Rq2	1Lq4	2Lq4	3Rq1		2Lq8	2Lq8
3	3Eq0	3Rq1	3Rq2	2Lq4	3Lq4	4Rq1		3Lq8	3Lq8
4	4Eq0	4Rq1	4Rq2	3Lq4	4Lq4	5Rq1		4Lq8	4Lq8
5	5Eq0	5Rq1	5Rq2	4Lq4	5Lq4	6Rq1		5Lq8	5Lq8
6	6Eq0	6Rq1	6Rq2	5Lq4	6Lq4	7Rq1		6Lq8	6Lq8
7	7Eq0	7Rq1	7Rq2	6Lq4	7Lq4	8Rq1		7Lq8	7Lq8
8	8Eq0	8Rq1	8Rq2	7Lq4	8Lq4	9Rq1		8Lq8	8Lq8
9	9Eq0	9Rq1	9Rq2	8Lq4	9Lq4	0Lq5	_Rq6	9Lq8	9Lq8

Трассировка приведенного алгоритма (будем отображать текущее внутреннее состояние и содержимое только используемой части ленты):

стоп

Как видно из примера, каждое внутреннее состояние отвечает за определенный шаг алгоритма:

q₁ – проход в конец первого числа;

q₂ – проход слева направо в конец второго числа;

q₃ – вычитание единицы из второго числа;

q₄ – проход справа налево в конец первого числа;

q₅ – прибавление единицы к первому числу;

q₆ – удаление второго числа после окончания сложения;

q₇ – проход справа налево по пустым ячейкам в конец первого числа;

q₈ – проход справа налево в начало первого числа;

q₀ – завершение работы алгоритма (содержит точки останова).

В таблице программы машины Тьюринга некоторые ячейки могут оставаться пустыми. В примере пустой остается ячейка, стоящая на пересечении строки символа «5» и столбца внутреннего состояния q₆. Это означает, что во внутреннем состоянии q₆ символ «5» обозреваться не может.