| N. → J | сдвиг вправо | |
| N. ← J | сдвиг влево | |
| N. 1 J | запись метки | |
| N. 0 J | удаление метки | |
| N. ? J1, J0 | условный переход по метке | |
| N. Stop | останов |
Для работы машины нужно задать программу и ее начальное состояние (т.е. состояние ленты и позицию каретки). После запуска возможны варианты:
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 |
|
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