Назад (Информатика).

Абстрактная машина Поста

Машина Поста состоит из ленты и каретки [считывающая и записывающая головка]. Лента бесконечна и разделена на секции одинакового размера.

В каждую секцию ленты заносится один символ двоичного информации, который подлежит обработке. Один из символов двоичного алфавита - метка "V", другой - пустота.

Если в секцию занесена "V" - секция отмеченная, если в секции "V" нет - секция пустая или неотмеченная.

Каретка может передвигаться вдоль ленты влево и вправо. Когда она неподвижна, она стоит против ровно одной секции ленты; говорят, что каретка обозревает эту секцию. А такая секция называется текущей или обозреваемой.

За единицу времени, которая называется шагом, каретка может сдвинуться на одну секцию влево или вправо. Кроме того, каретка может также распознать стоит или нет метка в обозреваемой ею секции, может заносить метку в пустую секцию и может удалять метку из отмеченной ячейки.

Команды, по которым каретка должна занести метку в отмеченную секцию или удалить метку из пустой секции являются недопустимыми.

Система команд машины Поста

Формат команды: nKm, где:

n - номер текущей команды;
K - команда из системы команд машины Поста [см. табл.];
m - ссылка - номер команды, которая будет выполняться следующей.

Последовательность команд из системы команд - программа, если:

1) на n - ом месте этой программы будет стоять команда с номером n.
2) ссылке m соответствует реальная команда в программе.

a→bСдвиг каретки вправо, содержимое ленты не меняется.
a←bСдвиг каретки влево, содержимое ленты не меняется.
aVbВ обозреваемую секцию ставится метка "V". Выполнение этой команды возможно только в том случае, если обозреваемая секция пустая, в противном случае команда считается невыполнимой.
a↕bКаретка стирает метку в обозреваемой секции. Выполнение этой команды возможно только в том случае, если обозреваемыя секция содержит метку, в противном случае команда считается невыполнимой.
a?b1,b2Команда передачи. Проверяется содержимое текущей секции, если метки нет, то происходит передача управления команде с номером b1, иначе, если метка есть - команде с номером b2. Содержимое ленты не меняется.
a![b]Команда останова машины. Содержимое ленты не меняется. У команды остановки ссылка не обязательна.

Пример программы сложения двух чисел для машины Поста

12 поиск начала первого числа: сдвигаемся влево
2?31 до тех пор, пока не встретим неотмеченную ячейку
34 сдвигаемся вправо, на 1-ую метку первого числа
45 удаляем ее
56 ищем конец первого числа: сдвигаемся вправо,
6?75 пока каретка не встанет на неотмеченную ячейку
7v8 ставим метку
89 проверяем заполнился ли промежуток между числами
9?110 если не заполнился- на первую строку, иначе - переход на конец
10! конец