Машина Поста
Машина Поста – это абстрактная (несуществующая реально) вычислительная машина, созданная для уточнения (формализации) понятия алгоритма. Представляет собой универсальный исполнитель, позволяющий вводить начальные данные и читать результат выполнения программы.
В 1936 г. американский математик Эмиль Пост в статье описал систему, обладающую алгоритмической простотой и способную определять, является ли та или иная задача алгоритмически разрешимой. Если задача имеет алгоритмическое решение, то она представима в форме команд для машины Поста.
В 1936 г. американский математик Эмиль Пост в статье описал систему, обладающую алгоритмической простотой и способную определять, является ли та или иная задача алгоритмически разрешимой. Если задача имеет алгоритмическое решение, то она представима в форме команд для машины Поста.
Тренажер для изучения универсального исполнителя К. Полякова
Пароль к архиву — kpolyakov.spb.ru
Машина Поста состоит из каретки (считывающей и записывающей головки) и бесконечной ленты, разбитой на ячейки. Каждая ячейка ленты может быть либо пустой («0»), или содержать метку («1»).
Программа состоит из пронумерованных строк. В каждой строке записывается одна из следующих команд:
> N переместить каретку вправо на 1 ячейку и перейти к строке с номером N;
< N переместить каретку влево на 1 ячейку и перейти к строке с номером N
0 N записать в текущую ячейку «0» (стереть метку) и перейти к строке с номером N
1 N записать в текущую ячейку «1» (поставить метку) и перейти к строке с номером N
? N, M если текущая ячейка содержит «0» (не отмечена), то перейти к строке с номером N, иначе перейти к строке M
. остановить программу
> 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
? 25, 0 остановить программу, если текущая ячейка содержит «1», иначе перейти к строке 25
В верхней части программы находится поле редактора, в которое можно ввести условие задачи в свободной форме.
Лента перемещается влево и вправо с помощью кнопок, расположенных слева и справа от нее. Двойным щелчком по ячейке ленты можно изменить ее
Пример:
Задания:
1. Прибавить 1 к числу
2. Учебник с. 217 задание 1, 2, 3, 4
Комментариев нет:
Отправить комментарий