Машина Поста

Эмиль Пост предложил абстрактную вычислительную машину – машину Поста. Она отличается от машины Тьюринга большей простотой. Обе машины «эквивалентны» и были созданы для уточнения понятия «алгоритм».

Машина Поста состоит из каретки (или считывающей и записывающей головки) и разбитой на секции ленты, считающейся условно бесконечной в обе стороны. В каждой клетке может быть записан символ из фиксированного алфавита. В любой конкретный момент головка обозревает одну клетку и способна работать только с ней.

Работа машины Поста определяется программой с конечным числом строк. Программы состоит из команд, имеющих по 3 поля, в которых записываются: № команды, операция и отсылка.

Команда машины Поста имеет следующую структуру:

n K m,

где n – порядковый номер команды, K – действие, выполняемое головкой, m – номер следующей команды, подлежащей выполнению.

Существует всего шесть команд машины Поста.

Для машины Поста определены операции 6 видов:

Движение головки на 1 клетку вправо.

Движение головки на 1 клетку влево.

Запись метки.

Удаление метки.

Условный переход по метке.

STOP – остановка (завершение работы машины Поста);

С точки зрения свойств алгоритмов, изучаемых с помощью машины Поста, наибольший интерес представляют причины останова машины при выполнении программы:

1. останов по команде «стоп»; такой останов называется результативным и указывает на корректность алгоритма (программы);

2. останов при выполнении недопустимой команды; в этом случае останов называется безрезультативным;

3. машина не останавливается никогда; в этом и в предыдущем случае мы имеем дело с некорректным алгоритмом (программой).

Машину Поста можно рассматривать как упрощенную модель ЭВМ. В самом деле, как ЭВМ, так и машина Поста имеют:

неделимые носители информации (клетки – биты), которые могут быть заполненными или незаполненными;

ограниченный набор элементарных действий – команд, каждая из которых выполняется за один такт (шаг).

Для работы машины нужно задать программу и ее начальное состояние (т. е. состояние ленты и позицию каретки). После запуска возможны варианты:

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

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

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

Обе машины работают на основе программы. Однако, в машине Поста информация располагается линейно и читается подряд, а в ЭВМ можно читать информацию по адресу; набор команд ЭВМ значительно шире и выразительнее, чем команды машины Поста и т.д.