Машина Поста (МП) — абстрактная вычислительная машина, предложенная Эмилем Леоном Постом (Emil L. Post), которая отличается от машины Тьюринга большей простотой. Обе машины «эквивалентны» и были созданы для уточнения понятия «алгоритм».

Принцип работы

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

            i K j,

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

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

   V j - поставить метку, перейти к j-й строке программы.
   X j - стереть метку, перейти к j-й строке программы.
   <- j - сдвинуться влево, перейти к j-й строке программы.
   -> j - сдвинуться вправо, перейти к j-й строке программы.
   ? j1; j2 - если в ячейке нет метки, то перейти к j1-й строке программы, иначе перейти к j2-й строке программы.
   ! – конец программы (стоп).

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

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

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

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

            v
    00111110111000
        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 (вы можете добавить проверку сами)

См. также

Другие абстрактные исполнители и формальные системы вычислений

• Нормальный алгоритм Маркова (продукционное программирование)
• Машина Тьюринга (автоматное программирование)
• Рекурсивная функция (теория вычислимости)
• Лямбда-исчисление (функциональное программирование)
• Brainfuck (императивное программирование)

Литература

Машина Поста / Гл. ред. физ.-мат. лит.. — 2-е изд., испр.. — М.: Наука, 1988. — 96 с. — (Популярные лекции по математике). — ISBN 5-02-013735-9.