- Машина поста
-
Машина Поста (МП) — абстрактная вычислительная машина, предложенная Эмилем Леоном Постом (Emil L. Post), которая отличается от машины Тьюринга большей простотой. Обе машины «эквивалентны» и были созданы для уточнения понятия «алгоритм».
Содержание
Принцип работы
МП состоит из каретки (или считывающей и записывающей головки) и разбитой на секции бесконечной в обе стороны ленты (см. пример ниже). Каждая секция ленты может быть либо пустой — 0, либо помеченной меткой 1. За один шаг каретка может сдвинуться на одну позицию влево или вправо, считать, поставить или уничтожить символ в том месте, где она стоит. Работа МП определяется программой, состоящей из конечного числа строк. Всего команд шесть:
N. → J сдвиг вправо N. ← J сдвиг влево N. 1 J запись метки N. 0 J удаление метки N. ? J1, J0 условный переход по метке N. Stop остановка где N. — номер строки, J — строка на которую переходит управление далее.
Для работы машины нужно задать программу и ее начальное состояние (т. е. состояние ленты и позицию каретки). После запуска возможны варианты:
- работа может закончиться невыполнимой командой (стирание несуществующей метки или запись в помеченное поле);
- работа может закончиться командой Stop;
- работа никогда не закончится.
Пример: вычитание натуральных чисел P — Q
Будем представлять натуральное (целое неотрицательное) число P набором из P+1 единиц и разделять числа нулём. Исходное положение каретки помечено символом «v»
v 00111110111000 P Q
Сложение двух чисел тривиально — достаточно поставить 1 между ними и стереть крайний правый символ у Q. Программа вычитания состоит из последовательного затирания крайних левых меток у Q и правых у P:
1. 0 - стираем левый символ у Q 2. → 3. ? 5, 4 4. Stop - стоп если затерли Q=0 5. ← 6. ? 7, 5 - цикл поиска P 7. 0 - стираем правый символ у P 8. → 9. ? 1, 8 - ищем Q
Отметим, что номер команды перехода не указывается, если переход происходит на следующую по порядку строку (для наглядности текста). В 6-ой строке возможно зацикливание, если Q > P (вы можете добавить проверку сами)
См. также
Другие абстрактные исполнители и формальные системы вычислений
- Нормальный алгорифм Маркова (продукционное программирование)
- Машина Тьюринга (автоматное программирование)
- Рекурсивная функция (теория вычислимости)
- Лямбда-исчисление (функциональное программирование)
- императивное программирование)
Литература
- Успенский В. А. Машина Поста, Наука, 1988. 98 с. Серия: Популярные лекции по математике, выпуск 54 http://math.ru/lib/plm/54
Wikimedia Foundation. 2010.