Эмулятор машины Поста
Классическая машина Поста
Машина Поста - это универсальный исполнитель (абстрактная
вычислительная машина), основанный на идеях работы американского математика
Э.Л. Поста, целью которой было уточнение понятия алгоритма. Согласно тезису
Поста, любой алгоритм может быть записан в виде программы для машины Поста.
Машина Поста состоит из каретки (считывающей и записывающей
головки) и бесконечной ленты, разбитой на ячейки. Каждая ячейка ленты может
быть либо пустой (« 0»), или содержать метку («1»).
Программа состоит из пронумерованных строк. В каждой строке
записывается одна из следующих команд:
> N переместить каретку вправо на 1 ячейку и перейти к строке с
номером N
< N переместить каретку влево на 1 ячейку и перейти к строке с номером
N
0 N записать в текущую ячейку
«0» (стереть метку) и перейти к строке с номером N
1 N записать в текущую ячейку
«1» (поставить метку) и перейти к строке с номером N
? N, M если текущая ячейка содержит «0» (не
отмечена), то перейти к строке с номером N, иначе перейти к строке M
. остановить программу
Номер строки перехода в командах >, <, 0 и 1 можно
не указывать, при этом происходит переход к следующей строке.
Для завершения работы программы достаточно сделать переход на
строку 0, например, так:
? 25, 0 остановить программу,
если текущая ячейка содержит «1» иначе
перейти к строке 25
Троичная машина Поста
В троичной машине Поста используется расширенный алфавит,
состоящий из трех символов: пробел, «0» и «1». Это позволяет программировать
задачи, в которых числа записаны в двоичной системе счисления. Команды,
отличающиеся от «стандартного» варианта машины Поста:
X N записать в текущую ячейку пробел (стереть
метку) и перейти к строке с номером N
0 N записать в текущую ячейку
«0» и перейти к строке с номером N
1 N записать в текущую ячейку
«1» и перейти к строке с номером N
Номер строки перехода может отсутствовать, при этом машина
переходит на следующую строку программы.
Команда ветвления содержит три метки, разделенные запятыми:
? N,M,L если
текущая ячейка пустая, то перейти к строке с номером N, иначе если текущая
ячейка содержит «0», то перейти к строке с номером M, иначе (если текущая ячейка содержит «1»)
перейти к строке L
Как работать с программой?
В верхней части программы находится поле редактора, в которое можно ввести
условие задачи в свободной форме.
Лента перемещается влево и вправо с помощью кнопок, расположенных
слева и справа от нее. Двойным щелчком по ячейке ленты можно изменить ее
содержимое (в «классическом» варианте заменяется «0» на «1» или наоборот, в
троичной машине Поста символы «пробел», «0» и «1» при последовательных двойных
щелчках меняются циклически).
С помощью меню Лента можно запомнить состояние ленты
во внутреннем буфере и восстановить ленту из буфера.
С помощью меню Алфавит можно переключать режим
работы машины (двоичный или троичный алфавит). В классическом режиме меню Вид
позволяет настроить вид ленты (точки, отметки-галочки, двоичный код).
В таблице в нижней части окна набирается программа. В первом
столбце записаны номера строк, он заполняется автоматически. Во втором столбце
из списка выбирается нужная команда, а в третьем вводится номер строки для
перехода (если это необходимо). Для добавления команды во втором столбце можно
использовать всплывающее контекстное меню.
Четвертый столбец может содержать комментарий к каждой строчке
программы. Добавить и удалить строки таблицы можно с помощью кнопок,
расположенных слева от таблицы.
Программа может выполняться непрерывно (F9) или по шагам (F8). Команда, которая сейчас будет
выполняться, подсвечивается зеленым фоном. Скорость выполнения регулируется с
помощью меню Скорость.
Задачи для машины Поста можно сохранять в файлах. Сохраняется
условие задачи, программа, состояние ленты и вид отметок. При загрузке задачи
из файла и сохранении в файле начальное состояние ленты автоматически
записывается в буфер.
| 
