Упражнение. 3.1. Покажите, что вычисление по алгоритму из примера 6 с начальной конфигурацией 6, 7, 0, 0, 0,

3.1. Покажите, что вычисление по алгоритму из примера 6 с начальной конфигурацией 6, 7, 0, 0, 0,... никогда не остановится.

Для удобства обозначим через P (a₁, a₂,..., a_n) вычисление по алгоритму P с начальной конфигурацией a₁, a₂,..., a_n, 0, 0,.... Если вычислительный процесс заканчивается с результатом b, будем писать P (a₁, a₂,..., a_n) = b.

Определение 3.1. Пусть f - функция от n неотрицательных целыхпеременных со значениями во множестве Z₀ неотрицательных целых чисел(функция ). Функция f называется вычислимой на МНР (или МНР–вычислимой), если существует такой алгоритм P, что

1) вычисление P (a₁, a₂,..., a_n) останавливается тогда и только тогда, когда (a₁, a₂,..., a_n) принадлежит области определения f;

2) если (a₁, a₂,..., a_n) принадлежит области определения f; то в заключительной конфигурации в регистре R₁ находится целое число b такое, что f (a₁, a₂,..., a_n) = b.

С этого момента под термином вычислимое будем подразумевать МНР–вычислимое.

Рассмотрим теперь несколько простых примеров вычислимых функций.

Пример 3.2. Докажите МНР-вычислимость функции x + y.

Решение. Получим x + y, прибавляя y раз 1 к числу x. Начальной конфигурацией алгоритма служит x, y, 0, 0, 0,.... Типичной конфигурацией в процессе вычисления является

R1	R2	R3	R4	R5	...
x + k	y	k	0	0	...

Определим алгоритм следующим образом:

I1	J(3, 2, 5)
I2	S(1)
I3	S(3)
I4	J(1, 1, 1)

Заданный алгоритм вычисляет функцию x + y.

Пример 3.3. Докажите МНР-вычислимость функции

Решение. Составим алгоритм для начальной конфигурации x, 0, 0,.... Типичной конфигурацией в процессе вычисления является:

R1	R2	R3	R4	R5	...
x	k	k + 1	0	0	...

Следующий алгоритм МНР-вычисляет функцию.

I1	J(1, 2, 6)
I2	S(2)
I3	J(1, 2, 6)
I4	S(3)
I5	J(1, 1, 2)
I6	T(3, 1)