Машина Поста может использоваться в школах, как простейший язык программирования с небольшим набором комманд, при переходе от теории к практическому применению алгоритмов на компьютере. Для лучшего понимания можно параллельно создавать графическую модель алгоритма и реализовывать ее при помощи машины Поста.
А вот моя версия этой программы:
Со временем, приведу примеры задач с готовыми вариантами решения.
Машина Поста (МП) — абстрактная вычислительная машина, предложенная Эмилем Леоном Постом (Emil L. Post), которая отличается от машины Тьюринга большей простотой. Обе машины «эквивалентны» и были созданы для уточнения понятия «алгоритм».
МП состоит из каретки (или считывающей и записывающей головки) и разбитой на секции бесконечной в обе стороны ленты. Каждая секция ленты может быть либо пустой — 0, либо помеченной меткой 1. За один шаг каретка может сдвинуться на одну позицию влево или вправо, считать, поставить или уничтожить символ в том месте, где она стоит. Работа МП определяется программой, состоящей из конечного числа строк. Всего команд шесть:
- N. > J сдвиг вправо
- N. < J сдвиг влево
- N. 1 J запись метки
- N. 0 J удаление метки
- N. ? J1, J0 условный переход по метке
- N. Stop остановка
где N. — номер строки, J — строка на которую переходит управление далее.Для работы машины нужно задать программу и ее начальное состояние (т. е. состояние ленты и позицию каретки). После запуска возможны варианты:
- работа может закончиться невыполнимой командой (стирание несуществующей метки или запись в помеченное поле);
- работа может закончиться командой Stop;
- работа никогда не закончится.
(ru.wikipedia.org)