Машина Поста

Машина Поста (МП) - абстрактная вычислительная машина, предложенная Эмилем Л. Постом (Emil L. Post), которая отличается от машины Тьюринга большей простотой. Обе машины эквивалентны и были созданы для уточнения понятия алгоритм.

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

МП состоит из каретки (или считывающей и записывающей головки) и разбитой на секции бесконечной в обе стороны ленты (см. пример ниже). Каждая секция ленты может быть либо пустой - 0, либо помеченной меткой 1. За один шаг каретка может сдвинуться на одну позицию влево или вправо, считать, поставить или уничтожить символ в том месте, где она стоит. Работа МП определяется программой, состоящей из конечного числа строк. Всего команд шесть:
N.   →   Jсдвиг вправо
    N.   ←   Jсдвиг влево
N.   1     Jзапись метки
N.   0     Jудаление метки
N.   ?   J1, J0   условный переход по метке
N.   Stopостанов
где N. - номер строки, J - строка на которую переходит управление далее.

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

Пример 1: вычитание натуральных чисел 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 (вы можете добавить проверку сами :)

Пример 2: умножение натуральных чисел R = P × Q

Пусть исходное состояние МП
           v
   0011...1101...10100
        P      Q   R
Внешний цикл по P программы умножения последовательно затирает P справа. Цикл по Q затирает Q справа и прибавляет 1 к R. После окончания внутреннего цикла Q восстанавливается для следующей итерации.
   
1.  0   // cycle P    22. →   // renew Q  
2.  ←                 23. 1
3.  ? 5,4             24. →
4.  Stop              25. ? 26,23
5.  →                 26. ←
6.  ? 7,5             27. 0
7.  →                 28. ←
8.  ? 7,9             29. ? 28,30
9.  ←                 30. ←
10. 0   // cycle Q    31. ? 1,30
11. ←
12. ? 13,22
13. →
14. ? 15,13
15. →
16. ? 15,17
17. 1
18. ←
19. ? 18,20
20. ←
21. ? 10,20
Очевидно, что использование в МП нескольких лент и (или) головок позволило бы избежать многочисленных перемещений головки по ленте и перезаписи чисел, существенно упростив программирование, однако эти ограничения на устройство МП никак не ограничивают возможности вычислений в принципе.

Тезис Чёрча

Тезис Чёрча утверждает, что машина Поста (или ее эквивалент) определяет то, что в математике понимают под алгоритмической ("механической") процедурой.

[1] В.А.Успенский Машина Поста, Наука, 1988. 98 с. Серия: Популярные лекции по математике, выпуск 54
[2] Р.Пенроуз "Новый ум короля. О компьютерах, мышлении и законах физики" 1989


Содержание
изменено 23 дек 05