1. Машины Тьюринга

Определение и примеры. Машина Тьюринга Τ представляет собой систему, работающую в дискретные моменты времени t = 0,1,2,... и состоящую из следующих частей:

1. Конечная лента, разбитая на конечное число ячеек. При этом в каждый момент времени t в ячейках записаны буквы из некоторого алфавита А = { } (где а₀= 0, а₁= 1, m > 1), называемого внешними алфавитом машины. Ячейка, в которой записан символ 0, называется пустой. В процессе работы машины каждая ячейка может менять свое состояние путем замены приписанного к ней символа а_i на другой символ . К существующим ячейкам можно пристраивать неограниченное число дополнительных ячеек, которые изначально считаются пустыми. Лента считается направленной, и ее ячейки будут просматриваться слева направо. Таким образом, если в какой-то момент времени лента имеет r ячеек, то состояние ленты полно­стью описывается словом , где — состояние первой (слева) ячейки, — состояние второй ячейки и т.д.

2. Управляющая головка, представляющая собой устройство, которое может перемещаться вдоль ленты так, что в каждый рассматриваемый момент времени оно находится напротив определенной ячейки и имеет некоторое состояние q_j из конечного множества внутренних состоянии Q = {q₀, q₁,... ,q_n} или внутренний алфавит, . Состояние q₀ называется заключительным и означает завер­шение работы машины, а состояние q₁ — начальным и означает начало работы машины.

3. Программа П, т.е. совокупность выражений T(i,j) (где i = 0,...,т, j = 1,...,n), каждое из которых имеет один из следующих видов:

• (сдвиг головки, находящейся в состоянии q_j напротив ячейки с буквой a_i, на одну ячейку влево с заменой состояния q_j на q_k);

• (сдвиг головки, находящейся в состоянии q_j напротив ячейки с буквой a_i,, на одну ячейку вправо с заменой состояния q_j на q_k);

• (замена буквы a_i в текущей ячейке на букву a_l, также замена состояния q_j головки на состояние q_k ).

Выражения T(i,j) называются командами. При этом коман­ды не могут начинаться со слов a_iq_0. Символы L и R не принад­лежат множеству AUQ.

Таким образом, машина Тьюринга Τ есть пятерка <A, Q, П, q₀, q₁>, а работа машины Τ состоит в изменении ее конфигура­ции К, состоящей из состояния ленты, состояния головки и по­ложения текущей ячейки. Дискретным моментам времени t = 0,1,2,... соответствуют конфигурации К₀,К₁,К₂,--- Конфигу­рация К₀ называется начальной, а конфигурация K_t, содержа­щая q₀, ~ заключительной. Конфигурации будут задаваться в виде машинных слов Μ = , где — состояние ленты, q_j — состояние головки, находящейся напротив ячейки с состоя­нием a_i, занимающей то же положение среди других ячеек, что и буква a_i в слове .

Опишем преобразование Μ М' машинного слова Μ в машинное слово М' за один шаг работы машины Т.

Пусть команда T(i,j) равна . Если — пустое слово , то М₂ = . Если же , то М₂ = .

Если T(i,j) — - аналогично.

Если T(i,j) = a_iq_j —> a_lq_к, полагаем М₂ = .

Будем говорить, что машинное слово М' получается из ма­шинного слова Μ с помощью машины Т, и писать Μ =>^Т Μ', ес­ли существует последовательность преобразований M_i —>^Т M_i+1, i = 0,..., к — 1, для которой М₀ = М, М_к = М'.

Преобразование Μ =>^Т Μ', при котором на каждом перехо­де M_i —>^T M_i+1 не достраиваются ячейки слева, обозначается через Μ Μ'.

Преобразование Μ =>^Т Μ', при котором на каждом переходе M_i —>^T M_i+1 не достраиваются ячейки ни слева, ни справа, обозначается через Μ | М'. (индекс Т можем опустить).

Зафиксируем алфавит А = {а₀, а₁ а₂, · , а_m}· Через будем обозначать слово a_i a_i a_i ...a_i алфавита A, состоящее из x букв a_i. Приведем список машин, которые будут использоваться в дальнейшем в качестве составляющих для других машин.

1. А (перенос нуля):

2. Б⁺ (сдвиг вправо):

3. Б^- (сдвиг влево):

4. В (транспозиция):

5. К (копирование):

6. Л (стирающая машина):

7. R (удаление 1): .

8. S (добавление 1): .

9. Сложение: . 10. Умножение: .

Приведем примеры программ для машины Сложение

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

	q1	q2	q3	q4	q5	q6	q7	q8	q9
0	R q2	R q3	Lq4	Lq5	Lq6 (где y=0)	0q0	Lq8	1q9	0q0
1		Rq2	R q3	0q4	0q7 (где y 0)	Lq6		Lq8	Lq9