Машина Тьюринга. Американский ученый Алан Тьюринг (A

Американский ученый Алан Тьюринг (A. turing) в 1937 г. Предложил следующий способ задания алгоритмов (рис 1.1)

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

У машины М имеется головка, позволяющая машине читать содержимое той (и только той) ячейки ленты, которая находится в данный момент напротив головки. Кроме этого, машина имеет внутреннюю память ограниченного (конечного) объема k. Не будем интересоваться тем, как устроена эта память и что в ней хранится. Лишь различим k состояний памяти и, соответственно, будем считать, что машина Тьюринга может в любой момент времени находиться в одном из k различных состояний. Эти состояния называют также состояниями машины Тьюринга. Каждая конкретная машина характеризуется набором команд, которые она может выполнять. Этот набор называется программой машины Тьюринга.

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

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

Формат команды имеет следующий вид:

A q b r D,

Где a – читаемый символ; q – текущее состояние; b – символ, записываемый в обозреваемую ячейку ленты вместо символа a; r - новое состояние; D - направление движения головки машины относительно ленты.

Символы выбираются из конечного алфавита А= {a1,…….,ai}. В дальнейшем будем использовать трехсимвольный алфавит { e, 0, 1}, при чем e будет означать «пустой (empty)» символ – отсутствие информации в ячейке, а с помощью нуля и единицы будут кодироваться все данные. Иногда используют двухсимвольный алфавит A= {e, 1 }. В этом случае числа кодируются только единицами: ноль кодируется одной единицей, число один кодируется двумя единицами, а число x кодируется x+1 единицами. Это – единичная система счисления. Однако она плоха с точки зрения сложности задач (см. гл. 5).

Множество состояний обозначим Q= {q1,…..,qk}. Направление движения D выбирается из множества { L, R, S}, где L – движение влево, R – движение вправо, S - отсутствие движения.

Таким образом, команда 1 q3 0 q6 L означает: если, находясь в состоянии q3, машина Тьюринга обозревает ячейку ленты, в которой записана 1, то машина должна записать в эту ячейку 0, произвести сдвиг головки относительно ленты влево на одну ячейку и перейти в состояние q6.

Это описание действия, соответствующего команде, говорит о том, что команда может рассматриваться как отображение пар (a, q) в тройки (b, r, D), т.е отображение

А x Q = A x Q x {L, R, S}.

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

Все действия производятся в дискретном времени. Иначе говоря, можно рассматривать целочисленные моменты времени t= 0,1,2,3,….. любое изменение происходит мгновенно в момент t=I и ничего не меняется между двумя соседними моментами времени.

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

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

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

Существует несколько способов представления программы машины Тьюринга (множества команд). Два наиболее употребительных:

1) двумерная таблица (рис 1.2);

2) диаграмма (нагруженный псевдограф).

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

Состояние   Символ	q1	….	q	…..	qk
a 1
…..
			br D
…..
a l

Рис 1.2 Табличная форма программы машины Тьюринга