Машина Поста

Машина Поста (МП) — абстрактная вычислительная машина, предложенная Эмилем Леоном Постом (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
 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home