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

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

1. V 4

2. С 3

3. 2

4. 5

5.? 4, 3

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

V

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

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

V

V

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

V

V

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

V

V

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

V

V

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

V

V

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

V

V

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

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

V

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

1. 2

2. 3

3. V 1.

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

V

1 шаг:

V

2 шаг:

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

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

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

1. 2

2. 3

3. стоп.

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

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

1. 1.

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

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

Дата добавления: 2014-01-06