Лабораторная работа № 3. Абстрактные автоматы. Машина Поста

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

Абстрактная машина Поста состоит из бесконечной ленты, разделенной на равные секции, а также считывающе-записывающей головки. Каждая секция может быть либо пуста (т.е. в нее ничего не записано), либо заполнена (отмечена – т.е. в нее записана метка). Вводится понятие состояние ленты как информация о том, какие секции пусты, а какие отмечены (по-другому: состояние ленты – это распределение меток по секциям, т.е. это функция, которая каждому числовому номеру секции ставит в соответствие либо метку, либо знак «пусто»). Естественно, в процессе работы машины состояние ленты меняется. Состояние ленты и информация о положении головки характеризуют состояние машины Поста.

Условимся обозначать головку знаком «» над обозреваемой секцией, а метку – знаком «M» внутри секции. Пустая секция никакого знака не содержит. За один такт (его называют шагом) головка может сдвинуться на одну секцию вправо или влево и поставить или удалить метку. Работа машины Поста заключает в переходе от одного состояния машины к другому в соответствии с заданной программой, которая строится из отдельных команд. Каждая команда имеет следующую структуру: xKy, где x – номер исполняемой команды; K – указание о выполняемом действии; y – номер следующей команды (наследника). Система команд машины включающая шесть действий, представлена в таблице:

№ п/п	Команда	Запись команды	Описание действий машины
1	Шаг вправо	X y	Сдвиг головки на одну секцию вправо
2	Шаг влево	X y	Сдвиг головки на одну секцию влево
3	Установить метку	XMy	В обозреваемую секцию ставится метка
4	Стереть метку	XCy	Из обозреваемой секции удаляется метка
5	Передача управления		При отсутствии метки в обозреваемой секции управление передается команде y1, при наличии – команде y2.
6	Остановка	x стоп	Прекращение работы машины

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

• команда <xMy> может быть выполнена только в пустой секции;
• команда <xCy> может применяться только к заполненной секции;
• номер наследника любой команды (y) должен соответствовать номеру команды, обязательной имеющейся в данной программе.

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

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

Целое число k записывается на ленте машины Поста посредством k+1 следующих подряд отмеченных секций, т.е. применяется унарная система счисления. Соседние записи чисел на ленте разделяются одной или несколькими пустыми секциями. Ниже приведен пример записи чисел 0, 2 и 3.

Пример 1.

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

Программа, обеспечивающая решение задачи, состоит из 4-х команд:

1.		3
		2
2.		1
3.	М	4
4.	стоп

Последовательное исполнение команд 1 и 2 приводит к тому, что головка за два такта работы машины сдвигается на одну позицию вправо. Это передвижение продолжается до тех пор, пока после очередного сдвига под головкой не окажется пустой ячейки – тогда по команде 3 в нее будет поставлена метка и по команде 4 машина остановится.

Пример 2.

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

Программа:

1.		2
		3
2.		1
3.		4
4.	М	5
5.	стоп