f,g を計算するプログラムをそれぞれ 󰒝,󰒞 とし、 次のプログラムを 󰒟 とする。 󰒝[0,⋯,k−1→k+1∣k+3] A: deck end 󰒞[0,⋯,k−1,k+2,k+1→k+1∣k+3] inck+2 backwardA これが h を計算することを示したい。 そのために、 レジスタが (x0,⋯,xk−1,y,0,⋯) である状態から 󰒟 を実行したときの動作を考える。 以下、 自然数 t(0≤t≤y) に対して、 以下の主張を帰納法によって示す。

• h(󰕷x,t) が定義されるならば、 行 A の命令が t 回目 (0 から数える) に実行されようとする瞬間が存在し、 その直前でのレジスタの状態は、 (x0,⋯,xk−1,y−t,h(󰕷x,t),t,?,⋯) である。
• h(󰕷x,t) が定義されないならば、 実行は停止しない。

まず t=0 の場合を示すために、 󰒟 の動作を初めから追おう。 h(󰕷x,0) すなわち f(󰕷x) が定義されるならば、 󰒝[0,⋯,k−1→k+1∣k+3] が実行されると k+1 番目のレジスタの値はその h(󰕷x,0) になり、 それ以外の k+3 番目より前のレジスタの値は変化しない。 したがって、 この時点でのレジスタの状態は、 (x0,⋯,xk−1,y,f(󰕷x),0,0,⋯) であり、 この状態で次に行 A が実行される。 h(󰕷x,0) すなわち f(󰕷x) が定義されないならば、 󰒝[0,⋯,k−1→k+1∣k+3] の実行が終了しないので、 󰒟 の実行全体も停止しない。 以上で t=0 の場合の主張は示された。

続いて帰納ステップのために、 ある t󰎘(0≤t󰎘≤y−1) について t=t󰎘 のときに主張が成り立つと仮定する。 まずは、 h(󰕷x,t󰎘+1) が定義される場合を考える。 原始再帰の定義により、 h(󰕷x,t󰎘+1)=g(󰕷x,t󰎘,h(󰕷x,t󰎘)) であるから、 h(󰕷x,t󰎘) と g(󰕷x,t󰎘,h(󰕷x,t󰎘)) はともに定義されているはずである。 すなわち、 帰納法の仮定により、 t󰎘 回目の行 A の直前では、 レジスタが (x0,⋯,xk−1,y−t󰎘,h(󰕷x,t󰎘),t󰎘,?,⋯) となっている。 ここで、 行 A すなわち deck が実行されると、 y−t󰎘>0 であるから、 k 番目のレジスタの値は y−t󰎘−1 に更新される。 続いて 󰒞[0,⋯,k−1,k+2,k+1→k+1∣k+3] が実行されるから、 k+1 番目のレジスタの値が g(󰕷x,t󰎘,h(󰕷x,t󰎘)) になる。 次に inck+2 が実行されると、 k+2 番目のレジスタの値は t󰎘+1 に更新される。 そして、 backwardA が実行され、 ポインタは行 A に戻る。 このときのレジスタの状態は、 (x0,⋯,xk−1,y−t󰎘−1,g(󰕷x,t󰎘,h(󰕷x,t󰎘)),t󰎘+1,?,⋯) である。 g(󰕷x,t󰎘,h(󰕷x,t󰎘))=h(󰕷x,t󰎘+1) であるから、 この場合は主張が示された。

h(󰕷x,t󰎘+1) が定義されない場合は、 h(󰕷x,t󰎘) が定義されていないか、 それが定義されても g(󰕷x,t󰎘,h(󰕷x,t󰎘)) が定義されないかのどちらかである。 前者の場合は、 帰納法の仮定から 󰒟 全体の実行は停止しない。 後者の場合は、 t󰎘 回目の行 A の実行の後で上の議論と同様に 󰒞[0,⋯,k−1,k+2,k+1→k+1∣k+3] の実行に移るが、 これが停止しない。 したがって、 どちらの場合でも 󰒟 全体の実行は停止しない。 以上で、 帰納ステップも示された。

この主張により、 h(󰕷x,y) が定義されるなら、 y 回目に行 A が実行されようとする直前でのレジスタの状態は、 (x0,⋯,xk−1,0,h(󰕷x,y),y,?,⋯) である。 この状態で行 A すなわち deck が実行されると、 k 番目のレジスタの値は 0 なのでポインタは直後の行に移り、 そこで 󰒟 の実行は終了し、 このときの k+1 番目のレジスタの値は h(󰕷x,y) である。 また、 h(󰕷x,y) が定義されないなら、 主張から 󰒟 の実行は停止しない。 これで、 󰒟 が h を計算することが示された。

原始再帰的であるとは、 初期関数から合成と原始再帰の繰り返しで得られる部分関数であった。 ところで、 命題 10.1 により初期関数は計算可能であり、 命題 10.4 と命題 11.1 により合成と原始再帰で計算可能性は保存される。 したがって、 原始再帰的な部分関数は全て計算可能になる。

全域関数 f:󱀍k+1→󱀍 を f(󰕷x,t) := 1∸chP(󰕷x,t) = { 0 ((󰕷x,t)∈P) 1 ((󰕷x,t)∉P) で定める。 仮定から chP は計算可能であり、 定理 11.2 によって y↦1∸y で与えられる関数は原始再帰的なので計算可能でもある。 したがって、 命題 10.4 によってこれらの合成である f も計算可能であることが分かる。 すなわち、 f を計算するプログラムが存在するので、 それを 󰒝 とする。 これを用いて、 次のプログラムを 󰒟 とする。 A: 󰒝[0,⋯,k−1,k→k+1∣k+2] B: deck+1 end inck backwardA これが h を計算することを示すために、 レジスタが (x0,⋯,xk−1,0,⋯) である状態から 󰒟 を実行したときの動作を考える。 自然数 t に対し、 以下の主張を帰納法によって示す。

• t 未満の全ての自然数 u に対して (󰕷x,u)∉P が成り立つならば、 行 B の命令が t 回目 (0 から数える) に実行されようとする瞬間が存在し、 その直前のレジスタの状態は、 (x0,⋯,xk−1,t,f(󰕷x,t),?,⋯) である。

まず t=0 の場合を示すために、 󰒟 の動作を初めから追おう。 初めに 󰒝[0,⋯,k−1,k→k+1∣k+2] が実行されるので、 k+1 番目のレジスタの値が f(󰕷x,0) になる。 つまり、 この時点でのレジスタの状態は、 (x0,⋯,xk−1,0,f(󰕷x,0),?,⋯) であり、 この状態で次に行 B が実行される。 これで t=0 の場合の主張は示された。

続いて帰納ステップのために、 ある自然数 t󰎘 について t=t󰎘 のときに主張が成り立つと仮定する。 また、 t󰎘+1 未満の全ての自然数 u に対して (󰕷x,u)∉P が成り立つとする。 仮定により、 t󰎘 回目の行 B の直前でのレジスタの状態は、 (x0,⋯,xk−1,t󰎘,f(󰕷x,t󰎘),?,⋯) である。 ここで、 特に (󰕷x,t󰎘)∉P であるから、 f(󰕷x,t󰎘)=1>0 である。 したがって、 行 B すなわち deck+1 が実行されると、 k+1 番目のレジスタの値は 0 に減り、 次は inck が実行される。 これにより、 k 番目のレジスタの値は t󰎘+1 に更新され、 ポインタは行 A に戻る。 行 A すなわち 󰒝[0,⋯,k−1,k→k+1∣k+2] が実行されると、 k+1 番目のレジスタの値は f(󰕷x,t󰎘+1) になる。 このときのレジスタの状態は、 (x0,⋯,xk−1,t󰎘+1,f(󰕷x,t󰎘+1),?,⋯) であるから、 これで帰納ステップも示された。

さて、 今 h(󰕷x) が定義されるとする。 󰔃t:=h(󰕷x) とおけば、 それは (󰕷x,t)∈P すなわち f(󰕷x,t)=0 を満たす最小の t である。 したがって、 󰔃t 未満の自然数 u に対しては (󰕷x,u)∉P が成り立つ。 よって主張により、 行 B の命令が 󰔃t 回目に実行されようとする直前でのレジスタの状態は、 󰔃t=h(󰕷x) と f(󰕷x,󰔃t)=0 であることに注意すれば、 (x0,⋯,xk−1,h(󰕷x),0,?,⋯) になっているはずである。 したがって、 この後に deck+1 が実行されると、 k+1 番目のレジスタの値は 0 なのでポインタは直後の行に移り、 そこで 󰒟 の実行は終了する。 このときの k 番目のレジスタの値は h(󰕷x) であるから、 この場合は定理が示された。

h(󰕷x) が定義されないなら、 それはすなわち (󰕷x,t)∈P を満たす t が存在しないということである。 そのため主張により、 任意の自然数 t に対して行 B が t 回目に実行されようとする瞬間が存在することになるが、 それは 󰒟 の実行が停止することはないということである。 以上により、 どちらの場合でも 󰒟 が h を計算することが示された。

一般再帰的であるとは、 初期関数から合成と原始再帰と最小化の繰り返しで得られる部分関数であった。 ところで、 命題 10.1 により初期関数は計算可能であり、 命題 10.4 と命題 11.1 と命題 11.3 により合成と原始再帰と最小化で計算可能性は保存される。 したがって、 一般再帰的な部分関数は全て計算可能になる。