Машина Поста

Машина Поста (МП) — абстрактная вычислительная машина, предложенная Эмилем Леоном Постом (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-й строке программы.

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

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

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

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

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