Принцип работы. Машина Поста состоит из каретки (или считывающей и записывающей головки) и разбитой на секции бесконечной в обе стороны ленты (см

Машина Поста состоит из каретки (или считывающей и записывающей головки) и разбитой на секции бесконечной в обе стороны ленты (см. пример ниже). Каждая секция ленты может быть либо пустой – 0, либо помеченной меткой 1. За один шаг каретка может сдвинуться на одну позицию влево или вправо, считать, поставить или стереть символ в том месте, где она стоит. Работа машины Поста определяется программой, состоящей из конечного числа строк. Для работы машины нужно задать программу и ее начальное состояние (т. е. состояние ленты и позицию каретки). Кареткой управляет программа, состоящая из строк команд. Каждая команда имеет следующий синтаксис:

i K j,

где i – номер команды, K – действие каретки, j – номер следующей команды (отсылка).

Всего для машины Поста существует шесть типов команд:

V j – поставить метку, перейти к j-й строке программы.

X j – стереть метку, перейти к j-й строке программы.

<– j – сдвинуться влево, перейти к j-й строке программы.

–> j – сдвинуться вправо, перейти к j-й строке программы.

? j1; j2 – если в ячейке нет метки, то перейти к j1-й строке программы, иначе перейти к j2-й строке программы.

! – конец программы (стоп).

У команды «стоп» отсылки нет. После запуска возможны варианты:

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

· работа может закончиться командой Stop;

· работа никогда не закончится.

3. Пример: вычитание натуральных чисел P – Q

Будем представлять натуральное (целое неотрицательное) число P набором из P+1 единиц и разделять числа нулём. Исходное положение каретки помечено символом «v»

Ú

P

Q

Сложение двух чисел тривиально – достаточно поставить 1 между ними и стереть крайний правый символ у Q. Программа вычитания состоит из последовательного затирания крайних левых меток у Q и правых у P:

1. 0 – стираем левый символ у Q

2. →

3.? 4, 5

4. Stop – стоп если затерли Q = 0

5. ←

6.? 5, 7 – цикл поиска P

7. 0 – стираем правый символ у P

8. →

9.? 8, 1 – ищем Q

Отметим, что номер команды перехода не указывается, если переход происходит на следующую по порядку строку (для наглядности текста). В 6-ой строке возможно зацикливание, если Q > P (вы можете добавить проверку сами).