12.2. Вычислимость рекурсии

Теорема 12.5. Пусть функции , вычислимы на МПД. Тогда функция вычислима.

Доказательство. Пусть G и Н — программы стандартного вида для вычисления функций G и H. Построим программу F, вычисляющую функцию . По начальной конфигурации по программе G вычисляется . Теперь, если Y ¹ 0, то применяем (многократно) программу Н для нахождения , , …, . Положим . Запоминаем в регистрах . Номер цикла K, где K = 0, 1, …, Y помещаем в . Промежуточное значение помещаем в . Программа F для вычисления F (здесь T =M+N):

T(1, M + 1)

…

T(N + 1, M + N + 1)

G[1, 2, …, N à M + N + 3]

IQ: J(T + 2, T + 1, P)

H[M + 1, … M + N, T + 2, T + 3 à T + 3]

S(T + 2)

J(1, 1, Q)

IP: T(T + 3, 1)

Следовательно, функция F вычислима, что и требовалось доказать.

< Предыдущая		Следующая >