Машина Поста
Маши́на По́ста — абстрактная вычислительная машина, предложенная Эмилем Постом в 1936 году, создана независимо от машины Тьюринга, но сообщение о машине Поста опубликовано на несколько месяцев позднее. Отличается от машины Тьюринга большей простотой, притом обе машины алгоритмически «эквивалентны» и обе разработаны для формализации понятия алгоритма и решения задач об алгоритмической разрешимости, то есть, демонстрации алгоритмического решения задач в форме последовательности команд для машины Поста.
Принцип работы
Машина Поста состоит из каретки (или считывающей и записывающей головки) и разбитой на ячейки бесконечной в обе стороны ленты. Каждая ячейка ленты может находиться в 2 состояниях — быть либо пустой — 0
, либо помеченной меткой 1
. За такт работы машины каретка может сдвинуться на одну позицию влево или вправо, считать, изменить символ в своей текущей позиции.
Работа машины Поста определяется программой, состоящей из конечного числа строк. Для работы машины нужно задать программу и её начальное состояние (то есть состояние ленты и позицию каретки). Кареткой управляет программа, состоящая из пронумерованных не обязательно упорядоченных строк команд, если в каждой команде указана строка, на которую нужно перейти. Обычно принимается, что если в команде переход не указан, то переход происходит на следующую строку. Каждая команда имеет следующий синтаксис:
i. K j
где i
— номер команды, K
— действие каретки, j
— номер следующей команды (отсылка).
Всего для машины Поста существует шесть типов команд:
V j
— поставить метку, перейти кj
-й строке программы;X j
— стереть метку, перейти кj
-й строке;← j
— сдвинуться влево, перейти кj
-й строке;→ j
— сдвинуться вправо, перейти кj
-й строке;? j1; j2
— если в ячейке нет метки, то перейти кj1
-й строке программы, иначе перейти кj2
-й строке;!
— конец программы («стоп», останов).
В команде «стоп» переход на следующую строку не указывается.
После запуска программы возможны варианты:
- работа может закончиться невыполнимой командой (стирание несуществующей метки или запись в помеченное поле);
- работа может закончиться командой «стоп»;
- работа никогда не закончится.
Пример
Для сложения и вычитания натуральных (целых неотрицательных) чисел P и Q их можно представить на ленте набором из P единиц и Q, отделённых друг от друга одним нулём; пусть исходное положение каретки находится на крайней левой «1» группы единиц Q (помечено символом «⇓
»):
⇓
…00111110111000…
╚═══╝ ╚═╝
P Q
Сложение двух чисел тривиально — достаточно поставить «1
» между числами и стереть одно крайнее правое «1
» у представления Q.
Программа вычитания таких чисел состоит из последовательного изменения крайних левых «1
» у представления Q и правых «1
» у представления P. В начале программы каретка установлена на крайнюю левую «1» у Q:
1. ←
— шаг влево2. ? 1; 3
— если в ячейке пусто, перейти к1
-шагу, если нет — к3
3. X
— удалить метку4. →
— шаг вправо5. ? 4; 6
— если в ячейке пусто, перейти к4
-шагу, если нет — к6
6. X
— удалить метку7. →
— шаг вправо8. ? 9; 1
— если в ячейке пусто, перейти к9
шагу, если нет — к1
9. !
— конец
В 5-й строке возможно зацикливание, если .
Литература
- Успенский Владимир Андреевич. Машина Поста / Гл. ред. физ.-мат. лит.. — 2-е изд., испр.. — М.: Наука, 1988. — 96 с. — (Популярные лекции по математике). — ISBN 5-02-013735-9.