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

Машина Тьюринга – это абстрактная структура, пример алгоритма. Машина Тьюринга (МТ) состоит из:

• управляющего устройства, которое может находиться в одном из состояний, образующих конечное множество ;

• ленты, разбитой на ячейки, в каждой из которых может быть записан один из символов конечного алфавита ;

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

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

Среди состояний управляющего устройства выделены начальное состояние изаключительное состояние . В начальном состоянии МТ находится перед началом работы, попав заключительное состояние МТ останавливается.

Для любого состояния и символаоднозначно заданы:

• следующее состояние ;

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

• направление сдвига головки ,обозначаемое одним из трех символов:L – влево, R – вправо, E – на месте.

Это задание может записываться либо системой команд, имеющих вид

,

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

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

Ко всякой незаключительной конфигурации применима ровно одна команда вида. Она переводитв. Это обозначается. Если существует последовательность конфигураций,, ... , переводящихв, так что, то это обозначается. Так если– стандартная начальная конфигурация, а– стандартная заключительная конфигурация, то правильно построенная МТ должна.

Для вычисления функций типа используется запись на ленте вунарном коде, т. е. натуральное число представляется последовательностью единиц, записанных подряд. Например, число х представлено в виде слова 11...1=, состоящего изх единиц.

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

Пример. Записать систему команд, реализующих функцию .

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

Данная последовательность действий описывается следующей системой команд:

;

;

;

;

;

;

.

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

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

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