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

Пример 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.

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

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

Пример 3. Рассмотрим программу:

1.? 4, 1

2. С 3

3. 3. стоп

4. 2.

Применим ее последовательно к начальным состояниям:

V

А)

 

V

Б)

 

V

В)

 

Для начального состояния А получим результативную остановку на четвертом шаге, для Б – бесконечную работу машины, для В – безрезультатную остановку на третьем шаге.

 

Вопросы для контроля

 

1. Что изучает теория алгоритмов?

2. Приведите примеры описаний понятия алгоритм

3. Перечислите свойства алгоритмов

4. Приведите примеры алгоритмов, решающих какие-либо житейские задачи.

5. Для чего нужно вводить строгое математическое определение алгоритма?

6. Опишите формализацию понятия алгоритма с помощью машины с неограниченными регистрами (МНР).

7. Дайте определение МНР-вычислимой функции. Приведите примеры МНР-вычислимых функций.

8. Сформулируйте тезис Черча.

9. Опишите формализацию понятия алгоритма с помощью машины Поста.

10. В чем сущность гипотезы Поста?