Описание программы-эмулятора машины Поста

Тренажёр «Машина Поста» – это учебная модель универсального исполнителя (абстрактной вычислительной машины), основанного на работах Э.Л. Поста по уточнению понятия алгоритма.

Рис. 12. Модель машины Поста

Машина Поста состоит из каретки (считывающей и записывающей головки) и бесконечной ленты, разбитой на ячейки. Каждая ячейка ленты может быть либо пустой («0»), или содержать метку («1»).

Программа состоит из пронумерованных строк. В каждой строке записывается одна из следующих команд (для расширенной модификации – троичной машины Поста используется дополнительный набор команд[2]):

> 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» или, наоборот, в троичной машине Поста символы «пробел», «0» и «1» при последовательных двойных щелчках меняются циклически).

С помощью меню Лента можно запомнить состояние ленты во внутреннем буфере и восстановить ленту из буфера.

С помощью меню Алфавит можно переключать режим работы машины (двоичный или троичный алфавит). В классическом режиме меню Вид позволяет настроить вид ленты (точки, отметки-галочки, двоичный код).

В таблице в нижней части окна набирается программа. В первом столбце записаны номера строк, он заполняется автоматически. Во втором столбце из списка выбирается нужная команда, а в третьем вводится номер строки для перехода (если это необходимо). Для добавления команды во втором столбце можно использовать всплывающее контекстное меню.

Четвертый столбец может содержать комментарий к каждой строчке программы. Добавить и удалить строки таблицы можно с помощью кнопок, расположенных слева от таблицы.

Программа может выполняться непрерывно (F9) или по шагам (F8). Команда, которая сейчас будет выполняться, подсвечивается зеленым фоном. Скорость выполнения регулируется с помощью меню Скорость.

Задачи для машины Поста можно сохранять в файлах. Сохраняется условие задачи, программа, состояние ленты и вид отметок. При загрузке задачи из файла и сохранении в файле начальное состояние ленты автоматически записывается в буфер.

Содержание работы

Запустить программу-эмулятор машины Поста. Ознакомиться с работой эмулятора и набором команд. Воспроизвести (не сохраняя в файл) предложенные выше примеры. По указанию преподавателя выбрать варианты из папки \..Example программы-эмулятора, а, также вариант из Приложения Е. По завершении работы результаты сохранить в файл.