Машина Поста состоит из (с11)

бесконечной ленты, поделенной на одинаковые ячейки (секции). Ячейка может быть пустой или содержать метку (принято обозначать символом V),

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

Рис.1. В каждый момент времени каретка указывает на одну из ячеек

Текущее состояние машины Поста описывается состоянием ленты и положением каретки. Состояние ленты – информация о том, какие секции пусты, а какие отмечены. Шаг – это движение каретки на одну ячейку влево или вправо. Состояние ленты может изменяться в процессе выполнения программы.

Кареткой управляет программа, состоящая из строк команд. Всего для машины Поста существует шесть типов команд. Каждая команда имеет следующий синтаксис:

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

Варианты окончания выполнения программы на машине Поста:

· останов по команде "стоп". Такой останов называется результативным и указывает на корректность алгоритма;

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

· машина не останавливается никогда. Уход в бесконечность, зацикливание. Машина Поста в результате работы алгоритма может вообще не остановиться (никогда не дойти до команды «стоп» и никогда не завершиться аварийной ситуацией). В этом и в предыдущем случае мы имеем дело с некорректным алгоритмом (программой).

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

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

Примеры:

Покажем, как можно воспользоваться командой условного перехода для организации циклического процесса. Пусть на ленте имеется запись из нескольких меток подряд, и головка находится над самой крайней меткой справа. Требуется перевести головку влево до первой пустой позиции .(с12)

Остановимся на представлении чисел на ленте машины Поста и выполнении операций над ними.

Число k представляется на ленте машины Поста идущими подряд k+1 метками (одна метка означает число «0»). Между двумя числами делается интервал как минимум из одной пустой секции на ленте. Нужно увеличить число 3 на единицу (изменить значение в памяти с 3 на 4). Допустим, точно известно, что каретка стоит где-то слева от меток и обозревает пустую ячейку. Тогда программа увеличения числа на единицу может выглядеть так: (с13)

Gt; 2

2? 1;3

Lt;- 4

V 5

5!

Зацикливание: зона работы для любого начального состояния ограничена одним и тем же числом ячеек, не зависящим от выбранного начального состояния ленты:

1. –> 2

2. <– 1