Программа машины Поста. Реализация типичных программ.

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

1) на первом месте в этом списке стоит команда с номером 1, на втором месте (если оно есть) – команда с номером 2 и т.д. Вообще на n-м месте стоит команда с номером n;

2) отсылка любой из команд списка совпадает с номером некоторой команды списка.

Число команд программы называется длиной программы.

Наибольший интерес представляют причины останова машины при выполнении программы:

- останов по команде «стоп». Такой останов называется результатным и указывает на корректность программы (алгоритма);

- останов при выполнении недопустимой команды. В этом случае останов называют безрезультатным;

- машина не останавливается никогда. В этом случае, как и в предыдущем, имеем дело с некорректной программой.

Примеры типичных программ.

1. Задано начальное положение каретки. На пустой ленте записать две метки: одну в секцию над кареткой, вторую справа от нее.

	1 V 2
	2 ® 3
	3 V 4
	4 стоп 4

2. Организация циклического процесса. На ленте имеется запись нескольких меток подряд, и каретка находится под самой крайней меткой справа. Перевести каретку влево до первой пустой позиции.

1 2  3 стоп 3

3. Представление чисел в машине Поста. Число K представляется на ленте машины Поста идущими подряд K+1 метками (одна метка означает число нуль). Между двумя числами делается интервал как минимум из одной пустой секции на ленте.

Например, запись чисел 3 и 5 выглядит на ленте следующим образом и не является позиционной:

4. Увеличить записанное число на 1. Для решения можно переместить каретку влево (или вправо) до первой пустой секции, а затем записать в нее метку.

Метка справа	Метка слева
1 ® 2 3 V 4 4 стоп 4	1 2 3 V 4 4 стоп 4

4. Предположим, что каретка расположена на расстоянии нескольких клеток слева от числа, к которому нужно прибавит 1. Программа усложнится, за счет появления «блока поиска числа» (первая и вторая строка).

1 ® 2      3 4 4 V 5 5 стоп 5

Сложение натуральных чисел.

Осуществить на машине Поста сложение чисел – значит составить такую программу, которая, будучи применена к ленте, содержащей записи чисел m₁, m₂,…,m_k (k ≥ 2), приводила бы к результативной остановке, причем после этой остановки на ленте оказалась бы запись числа m₁ + m₂ +…+ m_k.

Сделаем ряд уточнений:

- в начале на ленте не записано ничего, кроме чисел m₁, m₂,…,m_k, и в конце не было записано ничего, кроме их суммы;

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

- можно сделать различные предположения о расстоянии между массивами, служащими для записи чисел. В наиболее простом случае расстояние между соседними массивами равно 1;

- можно накладывать те или иные ограничения на количество слагаемых, считая это количество заранее заданным или произвольным.

Задача 1. Составить программу сложения двух чисел, записанных на расстоянии 1 друг от друга.

В силу сделанных предположений начальное состояние для задачи имеет вид:

Проще всего решить задачу, «заполнив» отметкой пустую секцию между массивами. Тогда, если слагаемыми были числа m₁ и  m₂, на ленте возникнет m₁+ m₂ +3 отмеченных секций, в то время как их должно быть m₁+ m₂ +1. Поэтому нужно стереть две лишние метки. Программа реализует описанные выше действия.

1 ® 2	4 ® 5	7 C 8
		8 9   9 С 10
3 V 4	6 7	10 стоп 10

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

1 С 2	4 С 5	7 V 8
2 ® 3	5 ® 6	8 стоп 8

Задача 2. Составить программу сложения произвольного количества чисел, записанных на ленте на расстоянии 1 друг от друга.

В силу сделанных предположений начальное состояние для задачи будет иметь вид:

Программа реализующая, поставленную задачу следующая:

1 С 2	5 ® 6
2 ® 3		10 ® 11
	7 стоп 7	11 С 12
4 V 5	8 9	12 ® 1

«Идея» программы состоит в том, что последовательно отщепляется по две метки слева (команд1 и команда 11), помещая взамен одну метку в ближайшую пустую секцию справа (команда 4); если следующая за ближайшей справа, пустой секцией также пусто, то значит, что пора заканчивать вычисление суммы (передача управления команде 7).

Задача 3. Составить программу сложения двух чисел, записанных на произвольном расстоянии друг от друга.

Начальное состояние для задачи имеет вид:

Программа реализующая, поставленную задачу следующая:

1 С 2
2 ® 3	7 8	12 ® 13
		13 С 14
4 V 5	9 ® 1	14 стоп 14
5 ® 6	10 11

 

«Идея» программы состоит в том, что левый массив «передвигается» вправо до тех пор, пока не сольется с правым. Передвижение массива осуществляется путем «перенесения» самой левой метки массива в ближайшую пустую секцию справа (метка отщепляется командой 1 и становится командой 4). Когда массивы сливаются (что обнаруживается командами 5 и 6), отмеченными оказываются m₁+ m₂ +2 секции, т.е. на одну больше, чем надо. Команды 10, 11, 12 перегоняют каретку в левый конец массива, где и стирается лишняя метка (команда 13). Таким образом, в заключительном состоянии каретка стоит непосредственно левее образовавшейся суммы.