От пальцевого счета до суперкомпьютеров      

Машина Поста

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

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

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

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

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

1. Движение головки на 1 клетку вправо.
2. Движение головки на 1 клетку влево.
3. Запись метки.
4. Удаление метки.
5. Условный переход по метке.
6. STOP - остановка (завершение работы машины Поста);

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

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