Программная вычислимость рекурсивных функций
В этом параграфе рассмотрим соотношение между программно вычислимыми и частично рекурсивными функциями. Справедлива следующая
Теорема 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:
В качестве входных переменных зафиксируем x1, …, xn, а выходной - x1. Пусть в исходном состоянии x1=a1, …, xn = an. Тогда в первой строке эти значения сохраняются в переменных z1, …, zn, которые своих значений далее не меняют. Поэтому для каждого i=1,…,m-1 после выполнения фрагмента
значением переменной yi является fin(a1,…, an), x1=a1, …, xn = an, а значения всех вспомогательных переменных равны 0. Тогда после выполнения
значением каждого 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.
Рассмотрим работу P на исходном состоянии ?, в котором ?(x1)=a, ?(y)=b. При b=0 цикл не выполняется и в результирующем состоянии ?1=P(?) имеем ?1(x1)=?1(?)(x1) =g1(a)= F2(a, 0). При b > 0 цикл будет выполняться b раз, так как в его теле v всякий раз увеличивается на 1, а значение y1=b и не меняется. Перед первым выполнением ?2 все ее рабочие переменные zi равны 0, x1=a, y=0, z=F2(a, 0), а после ее выполнения x1=h3(a,0,F(a,0))=F(a,1). Предположим теперь по индукции, что перед (i+1)-ым выполнением ?2 все ее рабочие переменные zi равны 0, x1=a, y=i и z=F2(a, i). После этого выполнения x1=h3(a,i,z)=h3(a,i,F(a,i))=F(a,i+1). Тогда присваивания z1:=0; … ; zm:=0; v:= v+1 после ?2 и z:=x1; x1:=u1; y:=v; перед ее следующим выполнением установят значения переменных ?2 так, что все ее рабочие переменные zi равны 0, x1=a, y=i+1 и z=F2(a, i+1). Следовательно, после b-го выполнения тела цикла x1=h3(a,b-1,F(a,b-1))=F(a,b).
Минимизация. Предположим, что функция Fn(x1,… ,xn) получена с помощью оператора минимизации (mu-оператора) из функции gn+1(x1,…, xn,y), т.е.
Пусть программа ?1 вычисляет gn+1, так что
Рассмотрим работу ? на входных значених xi = ai (i=1,…,n). В первой строке они сохраняются в переменных x'i, которые нигде в ? не изменяются, z получает значение 0, которое тоже не меняется по ходу вычисления, а u вначале получает значение 1. Поэтому условие цикла после первой строки истинно и он хотя бы один раз выполняется. Докажем, что для каждого i
входные переменные x1,…,xn,y имеют значения a1,…,an, i, соответственно, y'= i, а все рабочие переменные zj (j=1,…, m) равны 0.
Действительно, предположив это условие, получим, что после очередного выполнения фрагмента
значение u = x1 = g(a1,…,an,i), а рабочие переменные восстанавливают нулевые значения. Если g(a1,…,an,i)=0, то u=z и в условном операторе x1 получает значение y'=i. После этого условие цикла нарушено и ? завершает работу с выходным значением x1=i =F(a1,…, an). Если же g(a1,…,an,i)> 0, то u>z и в условном операторе y' увеличивает значение до (i+1). Тогда условие цикла выполнено и перед (i+2)-ым выполнением ?1 ее входные переменные x1,…,xn,y имеют значения a1,…,an, i+1, соответственно, y'= i+1, а все рабочие переменные равны 0.
Из доказанного утверждения непосредственно следует, что
Имеет место и утверждение, обратное теореме 8.1, которое мы приводим здесь без доказательства.
Теорема 8.2. Каждая программно вычислимая функция является частично рекурсивной.
