Программирование на машине Поста

Недавно на хабре появилось сразу два материала, посвященных языкам из «большой четверки тьюринговых трясин»: про алгоритм Маркова и Brainfuck. Думаю, для полноты картины будет интересно сравнить эти эзотерические системы с еще одним важным алгоритмическим примитивом — машиной Поста, которой я как раз занимаюсь.

Машина Поста (wiki; для простоты оттуда же взят вариант синтаксиса) похожа на всем известную машину Тьюринга, однако обладает интересными особенностями. Она содержит лишь 6 команд, кроме того, в ячейки-биты памяти могут записываться лишь 2 символа (двоичное кодирование информации). «Естественно», никакой дополнительной памяти, не зря же эзотерикой зовется!

Таким образом, при программировании на машине Поста помимо необходимости совладать с оккамовским синтаксисом надо думать о том, как записать на ленте все промежуточные результаты, не потеряв по пути обратную тропинку к остаткам входных данных. Почему «остаткам»? Зачастую ввиду отсутствия дополнительной памяти приходится обрабатывать входные данные итеративно (а иногда и рекурсивно). Надеюсь, вышеизложенное убедительно доказывает, что написание привычных алгоритмов на машине Поста — неплохая разминка для мозгов и весьма увлекательное занятие.

Пример

Рассмотрим одну из кратчайших реализаций умножения двух натуральных чисел. Числа n и m записываются на ленте в единичной системе счисления, разделяются одной пустой ячейкой. Вход/выход алгоритма может быть таким (отмечено начальное положение каретки):

   v
..01110110..   →   ..01111110..
    3 * 2      =        6

Идея алгоритма — краткое сложение. В каждом проходе цикла машина «откусывает» один бит от левого множителя и «копирует» самый правый имеющийся блок (сперва это второй множитель, затем — его последняя копия). Когда левый множитель «закончится», на ленте остается n блоков по m единиц. Их слияние дает искомое число n*m.

Код

 0. !        - команда остановки, выполнение начинается со строки №1
 1. 0        - главный цикл
 2. →
 3. ? 29, 4  - 29:левый множитель закончился
 4. →
 5. ? 6, 4
 6. →
 7. ? 8, 4
 8. ←
 9. ←
10. 0        - копирование правого блока
11. →
12. ? 13, 11
13. →
14. ? 15, 13
15. 1
16. ←
17. ? 18, 16
18. ←
19. ? 20, 18
20. 1
21. ←
22. ? 23, 10 - конец блока копирования
23. ← 
24. ? 25, 23
25. ←
26. ? 27, 23
27. →
28. → 1
29. →        - слияние копий второго множителя
30. 0
31. → 
32. ? 33, 31
33. 1
34. →
35. ? 0, 36  - выход из программы
36. ←
37. ? 29, 36 

Проверить корректность алгоритма можно в уме, на листочке, либо с помощью этой программы.

Это самая короткая известная мне реализация умножения. Однако, потенциально ее можно ужать еще сильнее, если придумать, как экономно объединить процессы создания копий и их слияния в единый массив.

Если вас заинтересовала тема, предлагаю подумать над следующими задачами:

• Вывод i-го числа Фибоначчи
• Деление двух натуральных чисел c остатком
• «Сборщик мусора». На ленте неизвестным образом распределено конечное количество (n) отмеченных ячеек. Необходимо «сгрести» их в одну кучу, т. е. машина должна оставить на ленте только блок в n отметок подряд.

P. S. «Большой четверкой» называю машину Тьюрига, Поста, систему Маркова и Brainfuck — самые изучаемые тьюринговые трясины.