Машина Поста
тренажер для изучения универсального исполнителя
Что это такое?
Тренажёр «Машина Поста» — это учебная модель
универсального исполнителя (абстрактной вычислительной машины), основанного на
работах Э.Л. Поста
по уточнению понятия алгоритма.
Согласно тезису Поста, любой алгоритм может быть записан в виде программы для машины Поста.
Доказано, что машина Поста по своим возможностям эквивалентна машине Тьюринга
и нормальным алгорифмам Маркова.
Машина Поста состоит из каретки (считывающей и записывающей головки) и бесконечной ленты,
разбитой на ячейки. Каждая ячейка ленты может быть либо пустой («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
Где почитать ещё?
- Успенский В.А. Машина Поста, М: Наука, 1988.
- Майер Р.В. Машины Поста и Тьюринга (komp-model.narod.ru).
- Бекман И.Н. Компьютерные науки. Лекция 7. Алгоритмы (profbeckman.narod.ru)
- Фалина И.Н., Радченко Е.Л. Изучение машины Поста в школьном курсе информатики
(inf.1september.ru)
- Соловьев А. Дискретная математика без формул (lib.rus.ec)
- Ершов С.С. Элементы теории алгоритмов, Челябинск, Издательский центр ЮУрГУ, 2009.
- Программирование на машине Поста (habrahabr.ru)
Что с этим делать?
В верхней части программы находится поле редактора, в которое можно ввести условие задачи в свободной форме.
Лента перемещается влево и вправо с помощью кнопок, расположенных слева и справа от нее.
Двойным щелчком по ячейке ленты можно изменить ее содержимое (в «классическом»
варианте заменяется «0» на «1» или наоборот, в
троичной машине Поста символы «пробел», «0» и «1»
при последовательных двойных щелчках меняются циклически).
С помощью меню Лента можно запомнить состояние ленты во внутреннем буфере и восстановить ленту из буфера.
С помощью меню Алфавит можно переключать режим работы машины (двоичный или троичный алфавит).
В классическом режиме меню Вид позволяет настроить вид ленты (точки, отметки-галочки, двоичный код).
В таблице в нижней части окна набирается программа. В первом столбце записаны номера строк, он
заполняется автоматически. Во втором столбце из списка выбирается нужная команда, а в третьем
вводится номер строки для перехода (если это необходимо). Для добавления команды во втором столбце
можно использовать всплывающее контекстное меню.
Четвертый столбец может содержать комментарий к каждой строчке программы. Добавить и
удалить строки таблицы можно с помощью кнопок, расположенных слева от таблицы.
Программа может выполняться непрерывно (F9) или по шагам (F8). Команда, которая сейчас
будет выполняться, подсвечивается зеленым фоном. Скорость выполнения регулируется с помощью меню Скорость.
Задачи для машины Поста можно сохранять в файлах. Сохраняется условие задачи, программа,
состояние ленты и вид отметок. При загрузке задачи из файла и сохранении в файле начальное
состояние ленты автоматически записывается в буфер.
Если вы заметили ошибку или у вас есть
предложения, замечания, жалобы, просьбы и заявления, пишите.
Технические требования
Программа работает под управлением операционных систем
линейки Windows на любых современных компьютерах.
Лицензия
Программа является бесплатной для некоммерческого использования.
Исходные тексты программы не распространяются.
Программа поставляется «as is», то есть, автор не несет никакой
ответственности за всевозможные последствия ее использования,
включая моральные и материальные потери, вывод оборудования из
строя, физические и душевные травмы.
При размещении программы на других веб-сайтах ссылка на первоисточник обязательна.
Без письменного согласия автора
ЗАПРЕЩАЕТСЯ:
- 1) публикация материалов в любой форме, в том числе размещение материалов на других Web-сайтах;
- 2) распространение неполных или измененных материалов;
- 3) включение материалов в сборники на любых носителях информации;
- 4) получение коммерческой выгоды от продажи или другого использования материалов.
Использование и скачивание материалов означает, что вы приняли условия этого лицензионного соглашения.
Скачать
Пароль к архиву — kpolyakov.spb.ru
В архив включены следующие файлы:
| post.exe |
основная программа — учебная модель «Машины Поста» |
| EXAMPLES |
подкаталог с примерами программ для тренажера «Машина Поста« |
После распаковки архива программа находится в работоспособном состоянии и
не требует никаких дополнительных установок.
Машина Поста
