Примеры выполнения программ.

Пример 1. Пусть имеется следующая программа машины Поста:

1. V 4

2. С 3

3. 2

4. 5

5. ? 4, 3

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

– начальное состояние

На первом шаге будет выполняться команда № 1. После первого шага состояние машины станет таким:

Следующей будет выполняться команда, на которую отсылает команда № 1, т.е. команда № 4:

Теперь надо выполнить команду под номером 5 (т.к.отсылка команды № 4 равна 5):

Состояние ленты при этом не изменится. Поскольку обозреваемая секция при этом пуста, то следующей должна выполняться команда, номер которой равен верхней (первой) отсылке, т.е. № 4:

Теперь снова выполняем команду под номером 5:

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

Команда № 3 делает отсылку на команду № 2, которая предписывает стереть метку в обозреваемой секции. Но машина сделать этого не может, т.к. обозреваемая в данный момент секция пуста. Следовательно, происходит безрезультатная остановка.

Пример 2. Пусть дано начальное состояние машины Поста:

Применим к этому начальному состоянию программу:

1. 2

2. 3

3. V 1.

Машина сделает два шага, а на третьем произойдет безрезультатная остановка:

1 шаг:

2 шаг:

3 шаг: машина должна напечатать метку в обозреваемой ячейке, но она там уже есть.

Безрезультатная остановка.

Применим к этому же начальному состоянию следующую программу:

1. 2

2. 3

3. стоп.

Машина сделает два шага, а затем на третьем произойдет результативная остановка.

Применим к этому же начальному состоянию программу:

1. 1.

Машина будет работать бесконечно.

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