Машина Поста

Машина Поста – это абстрактная (несуществующая реально) вычислительная машина, созданная для уточнения (формализации) понятия алгоритма. Представляет собой универсальный исполнитель, позволяющий вводить начальные данные и читать результат выполнения программы.

В 1936 г. американский математик Эмиль Пост в статье описал систему, обладающую алгоритмической простотой и способную определять, является ли та или иная задача алгоритмически разрешимой. 
Если задача имеет алгоритмическое решение, то она представима в форме команд для машины Поста.

Машина Поста состоит из ленты и каретки (называемой также считывающей и записывающей головкой).

Лента бесконечна и разделена на секции одинакового размера — ячейки.

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

Заметим, что наличие метки в ячейке можно интерпретировать как “1”, а отсутствие — “0”. Такое двоичное представление информации подобно представлению, используемому практически во всех современных ЭВМ.

Каретка может передвигаться вдоль ленты влево и вправо. Когда она неподвижна, она стоит против ровно одной ячейки ленты. 

За единицу времени каретка может совершить одно из трех действий: 

 - стереть метку, 

 - поставить метку, 

 - совершить движение на соседнюю ячейку. 

Состояние машины Поста складывается из состояния ленты и положения каретки.

Видео с 12.46 мин. до 15. 20 мин

Тренажер для изучения универсального исполнителя К. Полякова

Скачать 

Пароль к архиву — kpolyakov.spb.ru

Машина Поста состоит из каретки (считывающей и записывающей головки) и бесконечной ленты, разбитой на ячейки. Каждая ячейка ленты может быть либо пустой («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

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

Лента перемещается влево и вправо с помощью кнопок, расположенных слева и справа от нее. Двойным щелчком по ячейке ленты можно изменить ее 

Пример:

Откройте файл minus1 и выполните алгоритм по шагам

Задания:

1. Прибавить 1 к числу

2. Учебник с. 217 задание 1, 2
3. На ленте задан массив меток. Увеличить длину массива на 2 метки. Каретка находится либо слева от массива, либо над одной из ячеек самого массива
4. Даны два массива меток, которые находятся на некотором расстоянии друг от друга. Требуется соединить их в один массив. Каретка находится над крайней левой меткой первого массива.

Ответы на задания 3 и 4 см. файл Задания с ответами на диске