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

Следующим этапом уточнения понятия "алгоритм" является попытка представить алгоритмический процесс в виде работы некоего гипотетического устройства, работа которого может быть сведена к выполнению простейших действий. Тьюринг предложил в 1937 году концепцию такой машины, максимально простой по своей структуре. В машине Тьюринга вычислительный процесс разделяется на ряд элементарных операций, максимально простых. При этом внешняя память изображается в виде неограниченной с обеих сторон ленты, разбитой на ячейки. На любой стадии работы машины в каждой ячейке может храниться один символ из допустимого набора символов, называемого внешним алфавитом S={s₀, s₁, s₂,..., s_n}. Примем, что среди символов внешнего алфавита S имеется символ s₀, соответствующий пустому символу. Запись такого символа в ячейку оставляет ее пустой. Перед началом работы машины на ленту заносится начальная информация - любое слово внешнего алфавита S. Работа машины складывается из следующих один за другим тактов, во время которых происходит преобразование информации.

Вдоль бесконечной ленты перемещается управляющая головка, причем в каждый такт она находится напротив точно одной ячейки. За один такт управляющая головка может считать символ s_i, записанный в ячейку, и занести в ячейку новый символ s_j. Перемещение управляющей головки вдоль бесконечной ленты возможно только последовательно, то есть в каждый такт головка смещается на один шаг вправо (П) или влево (Л). Головка может также оставаться на месте (Н).

Машина Тьюринга имеет внутреннюю память, описываемую множеством состояний Q={q₀, q₁, ... , q_t}. Управляющая головка может находиться в одном из состояний, обозначенных символами из Q. Каждый такт работы машина Тьюринга находится в одном из состояний q_k и может либо сменить его на новое состояние q_m, либо остаться в старом состоянии. Среди множества состояний выделим одно особое состояние q₀, являющееся заключительным (стоп- символ). Предполагается, что в конце работы машина всегда перейдет в состояние q₀.

Как же работает машина Тьюринга? Каждый такт дискретного времени машина находится в состоянии q_k и считывает из ячейки, напротив которой она находится, символ s_i. При этом внутреннее состояние может измениться на q_m (k m, k=m), а в ячейку будет записан символ s_j (i j, i=j). Машина таким образом выполнит команду q_k s_i  q_m s_j. Если при указанных условиях машина также передвигает управляющую головку в соседнюю справа или слева ячейку, команда примет вид: q_k s_i  q_m s_j П или q_k s_i  q_m sj Л.

Головка также может оставаться на месте (Н): q_ks_j  q_ms_jH. Совокупность всех команд, которые может выполнить машина Тьюринга, называется ее программой. Программу удобно изображать в виде таблицы:

Q S	q1	q2	. . .	qk	. . .	qt
s0
s1
. . .				. . .
si			. . .	sj qm П	. . .
. . .				. . .
sn

В такой таблице строки помечены символами внешнего алфавита, а столбцы - символами внутренних состояний. Каждая клетка таблицы соответствует команде: если машина находится в состоянии q_k и считывает из ячейки символ s_i, то сменить состояние на q_m, записать в ячейку символ s_j и переместиться, например, вправо.

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

s_j q_k  s_j q_k Л

запишем в клетку таблицы только символ Л. Также для наглядности будем изображать состояние q₀ символом ! (стоп).

Впредь для большей наглядности будем пользоваться так называемыми конфигурациями. Под к-й конфигурацией будем понимать изображение ленты машины с информацией, сложившейся на ней к началу к-го такта, причем под обозреваемой ячейкой записан знак того состояния, которое подается в управляющую головку к началу этого же такта. Таким образом в к-й конфигурации явно указана входная пара знаков (s_i, q_k), а, следовательно, можно обращаясь к таблице определить соответствующую выходную тройку, а тем самым и (к+1)-ю конфигурацию.

Пример 1.6. Машина Тьюринга должна функционировать в соответствии с таблицей:

Q S	q1	q2	q3	q4
s0	q1 Л	q3 П	!	!
|	q2 Л	q2 Л	q4 П	* q3 П

В этом примере внешний алфавит содержит два символа: | и символ s₀, обозначающий, что ячейка пуста. Множество внутренних состояний машины - q₁, q₂, q₃, q₄, дополнено также состоянием ! - остановка. Для начала работы машины необходимо заполнить некоторые клетки ленты символами, отличными от s₀, задать начальное положение управляющей головки относительно ленты и состояние, отличное от !. После этого машина начинает работать в соответствии с таблицей. Пусть начальная информация на ленте имеет вид:

s0

|

|

|

|

|

|

s0

s0

| q₂ | . . .  | q₂ | | q₁ | | q₁ |

такт 7 такт3 такт 2 такт 1

и управляющая головка расположена справа от первого символа | . Первые 7 тактов работы управляющая головка :

1) смещается влево и находит символ | (такт 1),

2) переходит в состояние q₂ и двигается влево до тех пор, пока не встретится пустая ячейка (такты 2-7). При нахождении пустой ячейки состояние управляющей головки меняется на q₃, и начинается движение в обратную сторону (такт 8).

s0

|

*

|

*

|

*

s0

s0

| q₂ | | q₃ || q₄ | | q₃ | | q₄ | …  | ! |

такт 8 такт9 такт10 такт11 такт12 … такт 15

Такты 9,10 и далее, управляющая головка двигается вправо и, заменяет каждую вторую палочку символом "*" (состояние q₄). После этого состояние меняется на q₃ и далее выполняются аналогичные действия. Признаком остановки алгоритма будет нахождение первой пустой ячейки справа. В нашем примере это произойдет на пятнадцатом такте. Таким образом, машина Тьюринга, чья работа описана вышеприведенной таблицей, решает следующую задачу: в слове из палочек, первоначально записанном на ленте, слева направо каждая вторая палочка заменяется на *.

Из примера видно, что человек легко может пользоваться таблицей машины Тьюринга. Самостоятельно рассмотрите примеры, когда на ленте записано 9 палочек, 10 палочек.

Пример 1.7.

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

Исходной информацией для алгоритма является записанный на ленте массив палочек. Прежде чем кодировать таблицу, необходимо продумать последовательность действий алгоритма. Для данной задачи можно предложить, например, такой путь решения (естественно, он не является единственно возможным): припишем к концу исходного слова символ *. Далее, стерев одну палочку исходного слова, запишем три новых палочки в свободных ячейках справа от звездочки. Будем продолжать этот процесс до тех пор, пока все палочки исходного слова не будут использованы. Признаком остановки алгоритма станет отсутствие палочек слева от звездочки. Из приведенных рассуждений следует, что внешний алфавит будет включать символы палочка, звездочка и пробел (пустой символ). Для правильной работы машины Тьюринга необходимо задать начальное положение управляющей головки. Пусть перед началом работы управляющая головка находится справа от первого символа | и внутреннее состояние машины - q₁. Первый такт работы машина обозревает пустую ячейку справа от палочки и, находясь в состоянии q₁, записывает в ячейку символ *. При этом машина изменит состояние на q₂ и головка сместится влево (левая верхняя клетка таблицы). Заметим, что в дальнейшем не предусмотрен возврат в состояние q₁, чтобы избежать приписывания "лишних" символов *.

Q S	q1	q2	q3	q4	q5	q6
s0	* q2 Л	q3 П		| q5 П	| q6 П	| q2 Л
|		Л	s0 q4 П	П
*		Л		П

Находясь в состоянии q₂, головка перемещается влево до появления пустого символа (ищем левый конец исходного слова). Как только он найден (s₀ q₂) головка возвращается вправо и происходит смена состояния на q₃. Сменить состояние необходимо, так как дальше выполняются действия, отличные от предыдущих, а именно, стирается одна, самая левая палочка ( | q₃  s₀ q₄ П). Почему мы опять меняем состояние? Если машина останется в состоянии q₃, все последующие палочки также будут стираться, что не соответствует замыслу. Следующая подзадача - найти пустую ячейку справа и записать подряд три новых палочки. Для этого головка смещается вправо, пропуская все палочки и разделитель *. Наконец, находясь в состоянии q₄, управляющая головка находит пробел. Естественным представляется записать в эту пустую ячейку палочку и переместиться вправо. Вспомним, однако, что нужно записать ровно три новых палочки, а не одну и не бесконечно много. Как этого добиться? Роль "счетчика палочек" могут играть состояния машины: q₅ будет соответствовать записи второй палочки, а q₆ - третьей.

К моменту записи третьей палочки завершен первый цикл работы машины: одна палочка исходного слова заменена тремя новыми палочками. Очевидно, теперь надо повторить все действия: перемещение влево до появления пустого символа и т.п. Чтобы организовать такое повторение, запись палочки в состоянии q₆ будет сопровождаться переходом в состояние q₂ и смещением влево. Если в состоянии q₂ встретится символ *, движение влево необходимо продолжить, поэтому в соответствующую клетку таблицы добавим команду Л.

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

Q S	q1	q2	q3	q4	q5	q6
s0	* q2 Л	q3 П	q0	| q5 П	| q6 П	| q2 Л
|	!	Л	s0 q4 П	П	!	!
*	!	Л	s0 !	П	!	!

Когда алгоритм заканчивает работу? Прежде всего тогда, когда в исходном слове не осталось палочек. В такой ситуации перемещение управляющей головки влево до пробела и переход в состояние q₃ приведет к тому, что головка считает из ячейки символ *, а не |. Необходимые действия: стереть звездочку и остановиться (состояние !). Эта ситуация является нормальным завершением работы алгоритма. Придумать ситуацию, когда в состоянии q₃ встретится пустая ячейка, или когда в состояниях q₅, q₆ на ленте будут найдены непустые символы (палочка или звездочка) просто не удастся, так как это противоречит исходным данным. Чтобы не оставлять соответствующие клетки пустыми, в них можно занести символ остановки q₀. Теперь таблица полностью готова к работе. Проверить ее действие на примерах предлагается самостоятельно. Ниже приведен один из вариантов расположения исходной информации на ленте.

s0

s0

|

|

|

|

s0

s0

s0

s0

˄

| q₁ |

Пример 1.8.

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

Q S	q1	q2	q3
|	s0 q2 Л		| q3 П
s0			s0 q1 Л
2	2 ! Н
1	1 ! Н	2 q3 П
0	0 ! Н		0 q3 П

Начальное положение управляющей головки - против первого символа s₀, ограничивающего справа массив палочек. Начальное состояние - q₁.

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

Отметим, что в зависимости от того, какая была подана начальная информация, возможны два случая:

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

2) остановка никогда не наступает (сигнал об остановке никогда не появляется). В таком случае говорят, что машина Тьюринга не применима к начальной информации.

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