Введение в схемы, автоматы и алгоритмы


Программная вычислимость рекурсивных функций


В этом параграфе рассмотрим соотношение между программно вычислимыми и частично рекурсивными функциями. Справедлива следующая

Теорема 8.1. Каждая частично рекурсивная функция программно вычислима.

Доказательство индукцией по определению ч.р.ф.

Базис: программная вычислимость простейших функций была установлена в примерах 1.1, 1.2 и 1.4.

Индукционный шаг: покажем программную вычислимость операторов суперпозиции, примитивной рекурсии и минимизации.

Суперпозиция. Пусть Fm и f1n,…, fmn

- арифметические функции, вычислимые программами ?, ?1, … , ?m так, что ??, x1(x1,…, xm) = Fm(x1,…, xm), и ??i, x1(x1,…, xn) = fin(x1,…, xn) при i=1,…,n. Пусть переменные y1, …, ym, z1,…, zn

не используются в программах ?, ?1, … , ?m. Кроме того, пусть все вспомогательные переменные этих программ - это w1, … , wr. Рассмотрим следующую программу P:

 z_1:= x_1;\ldots ; z_n:= x_n; \\ \Pi_1; y_1 := x_1; x_1:= z_1;\ldots ; x_n:= z_n; \\ w_1 := 0; \ldots ; w_r:=0; \\ \Pi_2; y_2 := x_1; x_1:= z_1;\ldots ; x_n:= z_n; \\ w_1 := 0; \ldots ; w_r:=0; \\ \ldots \\ \Pi_m; y_m:= x_1; x_1:= y_1; \ldots ; x_m := y_m; \\ w_1 := 0; \ldots ; w_r:=0; \\ \Pi

В качестве входных переменных зафиксируем x1, …, xn, а выходной - x1. Пусть в исходном состоянии x1=a1, …, xn = an. Тогда в первой строке эти значения сохраняются в переменных z1, …, zn, которые своих значений далее не меняют. Поэтому для каждого i=1,…,m-1 после выполнения фрагмента

\Pi_i; y_i := x_1; x_1:= z_1; \ldots; x_n := z_n; \\ w_1 := 0; \ldots; w_r := 0;

значением переменной yi является fin(a1,…, an), x1=a1, …, xn = an, а значения всех вспомогательных переменных равны 0. Тогда после выполнения

\Pi_m; y_m := x_1; x_1 := y_1; \ldots ; x_m := y_m;

значением каждого xi также является fin(a1,…, an), а после выполнения ? значение x1 равно ?P,x1(x1,…,xm)= Fm(f1n(a1,…, an), …, fmn(a1,…, an)). Таким образом, ?P, x1 = [F; f1, …, fn].

Примитивная рекурсия. Рассмотрим для простоты случай n=1. Пусть функция F2(x1,y) получена с помощью оператора примитивной рекурсии из функций g1(x1) и h3(x1, y, z), т.е. F2 =R(g1,h3). Предположим, что существуют программы ?1 и ?2, вычисляющие функции g1 и h3 так, что ??1,x1}(x1)=g1(x1) и ??2,x1(x1, y,z)=h3(x1,y,z). Пусть вспомогательные переменные ?2 - это z1,…, zm и они не встречаются в ?1, а переменные u1, y1 и v не используются в программах ?1 и ?2. Рассмотрим программу P: u1 :=x1; y1:=y; v:=0; ?1; пока v < y1 делай z:=x1; x1:=u1; y:=v; ?2; z1:=0; … ; zm:=0; v:= v+1 все В качестве входных переменных P возьмем x1 и y, а выходной - x1.




Начало  Назад  Вперед



Книжный магазин