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


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


Рассмотрим работу 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), т.е.

F^n(x_1,\ldots, x_n) =\mu y[ g^{n+1}(x_1,\ldots, x_n,y)=0].

Пусть программа ?1 вычисляет gn+1, так что

\Phi_{\Pi_1, x_1}(x_1,\ldots, x_n,y)=g^{n+1}(x_1,\ldots, x_n,y)
, и пусть рабочие переменные ?1 - это z1,…, zm. Зафиксируем переменные x1',… , xn', y';, u, z, не входяшие в
Var_{\Pi_1}
. Рассмотрим следующую программу ?:

 x_1':=x_1; \ldots ; x_n':= x_n; z:=0; u:=0; u:=u+1; y' :=0;\\ \textbf{пока}\ z < u\ \textbf{делай}\\ x_1:=x_1'; \ldots ; x_n:= x_n'; y:= y'; \ \Pi_1;\ u:=x_1; z_1:=0;\ldots ; z_m:=0;\ \\ \textbf{если}\ u=z\ \textbf{то}\ x_1 := y'\ \textbf{иначе}\ y':= y' +1\ \textbf{конец}\\ \textbf{все}

Рассмотрим работу ? на входных значених xi = ai (i=1,…,n). В первой строке они сохраняются в переменных x'i, которые нигде в ? не изменяются, z получает значение 0, которое тоже не меняется по ходу вычисления, а u вначале получает значение 1. Поэтому условие цикла после первой строки истинно и он хотя бы один раз выполняется. Докажем, что для каждого i

1, (i+1)-ая итерация цикла выполняется тогда и только тогда, когда g(a1, …, an,0)=b1 >0, …, g(a1, …, an, i-1)=bi-1 > 0, ? останавливается после (i+1)-ой итерации цикла с результатом x1=i тогда и только тогда, когда g(a1, …, an,i)=0. При этом перед выполнением ?1

входные переменные x1,…,xn,y имеют значения a1,…,an, i, соответственно, y'= i, а все рабочие переменные zj (j=1,…, m) равны 0.




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



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