Лабораторная работа № 4. Абстрактные автоматы. Машина Тьюринга

(4 неделя, 2 часа)

Рассмотрим устройство, которое состоит из бесконечной в оба конца ленты и автомата. Лента разбита на ячейки, в которые вписываются символы из внешнего алфавита { , a₀, a₁,..., a_N}, причем символ " " означает пустой символ. Автомат может находиться в одном из состояний {q₁,..., q_r} и осуществлять одно из трех движений в каждый момент времени, {R, L, S}: R - переместиться на одну ячейку вправо, L - переместиться на одну ячейку влево, S - остаться на месте. Работу такого устройства можно задать с помощью специальной таблицы, называемой программой.

В самом левом столбце располагаются символы алфавита { , a₀, a₁,..., a_N} (внешний алфавит машины). Множество {q₁,..., q_r} - внутренний алфавит машины. Некоторые клетки этой таблицы могут быть пустыми. В клетки этой таблицы записываются команды машины, т.е. тройки символов cDq, где c - символ из внешнего алфавита машины, q - символ из внутреннего алфавита машины и D - символ из алфавита, описывающего движение, т.е. из множества {R, L, S}. Если в некоторый момент времени головка автомата обозревает на ленте символ a _i и автомат находится в состоянии q _j, то машина должна выполнить команду, стоящую на пересечении строки с номером a _i и столбца с номером q _j. Если в означенной клетке находится команда cDq, то машина должна записать в текущую ячейку символ c, перейти в состояние q и осуществить движение D. Если означенная клетка окажется пустой, то машина останавливается.

	q1	qj	qr
a0
a1
.
.
.
ai		cDq
.
.
.
aN

Конфигурацией машины Тьюринга называется цепочка вида a qa b, где a a b - содержимое ленты, q - текущее состояние головки, а её позиция указывает обозреваемую ячейку между a и b (см. рисунок). Пишем a^x для сокращения слова . Предполагается, что начальная конфигурация всегда имеет вид q ₀ a b, т.е. головка в этих конфигурациях всегда сдвинута к левому концу ленты. В результате применения программы возможны 2 ситуации:

1. В некоторый момент времени появится пустая команда (или пустая клетка) и машина остановится.

1. Пустая клетка никогда не появится и машина не остановится.

Пример 3.

Добавить 1 к унарному числу посредством машины Тьюринга.

Внешний алфавит может быть задан множеством A ={ ,1}, где 1 соответствует заполненной секции, а  - пустому знаку, причем заполненные следуют друг за другом подряд. Внутренний алфавит задается множеством Q ={ q, z }, где q соответствует рабочему состоянию логического устройства, а z – остановке. Набор всех правил преобразования (логическая функция) может быть представлен функциональной схемой:

A	q	z
	z 1 S	z  S
1	q 1 R	z 1 S

Составляется функциональная схема в виде таблицы таким образом, что знаки, обозначающие колонки и строки, определяют входные параметры логического устройства, а в ячейке таблицы на их пересечении стоит выходная команда. В частности, если головка машины обозревает секцию ленты со знаком 1 и машина находится в рабочем состоянии (q), то результатом её работы на данном такте должно стать повторение 1 в данной секции и переход на одну секцию вправо R - эта команда записывается как q 1 R. Если же в обозреваемой секции , а состояние логического устройства (ЛУ) q, то  будет заменён 1, сдвига ленты производиться не будет и машина остановится - z 1 S.

Пусть начальной является конфигурация 1 q 1111. Тогда работа машины в соответствии с описанной логической функцией будет происходить следующим образом:

Такт 1. Обозревается 1, в ЛУ состояние q. Выходная команда q 1 R, что эквивалентно перемещению головки по отношению ленты на 1 шаг вправо. Следовательно, образуется промежуточная конфигурация 11 q 111.

Такт 2. Аналогичным образом осуществляется переход к конфигурации 111 q 11.

Такт 3. Переход к конфигурации 1111 q 1.

Такт 4. Переход к конфигурации 11111 q .

Такт 5. Обозревается , в ЛУ состояние q. Выходная команда z 1 S – вместо  в ячейку записывается 1, сдвига нет, работа прекращается.

Конечная конфигурация 111111 z.

Пример 4.

Имеется запись многоразрядного числа n в десятичной системе счисления. Построить машину Тьюринга, которая обеспечивала бы вычисление значения n +1.

Используем внешний алфавит А ={0,1,…,9,0, }, в котором символ  соответствует пустому знаку. Внутренний алфавит, как и в предыдущем примере, образуется двумя состояниями – рабочим (q) и остановкой (z) (Q ={ q, z }). Исходное число n, а также результат – n +1 – записываются в десятичной системе, причем, цифры размещаются по одной в соседних ячейках без пропусков. Функциональную схему представим таблицей:

a	0	1	2	3	4	5	6	7	8	9
q	z 1 S	z 2 S	z 3 S	z 4 S	z 5 S	z 6 S	z 7 S	z 8 S	z 9 S	q 0 L	z 1 S

Пусть начальной конфигурацией будет 21 q 9.

Такт 1. q 9 q 0 L, т.е. 9 будет замещена на 0 и головка сдвинется на разряд десятков – промежуточная конфигурация 2 q 10.

Такт 2. q 1 z 2 S, т.е. 1 будет заменена на 2 и произойдет остановка с конечной конфигурацией 2 z 20, т.е. получен результат сложения 219+1.

Пусть начальной конфигурацией будет 99 q 9.

Такт 1. q 9 q 0 L, т.е. сформируется промежуточная конфигурация 9 q 90.

Такт 2. q 9 q 0 L, возникнет конфигурация q 900.

Такт 3. q 9 q 0 L, возникнет q 000.

Такт 4. q z 1 S – возникнет z 1000 и работа прекращается.

Задания

1. Используя алгоритмическую машину Тьюринга, произведите сложение двух чисел в унарной системе счисления (например, 111+11).
2. Дано слово из знаков a и b произвольной длины (например, aab – bab), причем, заранее не известно, какой знак первый (a или b). Необходимо первый знак переместить в конец слова.
3. Добавление 1 к числу в произвольной заданной системе счисления.