日記 (2026 年 1 月 16 日)
今回からは、 どのような関数が計算可能なのかをより具体的に見ていく。
しばらくの目標は、 全ての一般再帰関数が計算可能であることを示すことである。
本題に入る前に、 プログラムを見やすくするための記法を導入しておこう。
forward 命令や backward 命令は、 ポインタの移動先をその命令自身から何個後もしくは前にするかを引数にとる。
例えば、 forward3 はポインタを 3 つ後ろに進める。
そのため、 これらの命令の実行後にポインタがどこに飛ぶかを確認するには、 引数の数の分だけ数えながら目で追う必要があり、 若干分かりづらい。
そこで、 命令にラベルを付けておいて、 forward や backward の引数にそのラベルを書いてしまうことにする。
例えば、 backwardA と書いてあったら、 A とラベル付けされた命令にポインタを飛ばすことを意味する。
もし A とラベル付けされた命令が backwardA の 3 つ前にあるのであれば、 これは backward3 と書いてあったことにするわけである。
また、 書かれているプログラムの最後の命令のちょうど次の位置にポインタを飛ばす forward 命令のことを、 単に end と書いてしまうことにする。
例えば、 もし end の後ろに命令が 2 つ書かれているのであれば、 これは forward3 と書いてあったことにするわけである。
このような記法を用いれば、 前回で恒等関数を計算するプログラムとして挙げた
dec0 forward3 inc1 backward3
というプログラムは、
A: dec0 end inc1 backwardA
と書くことができる。
こちらの方が見やすいので、 以降は適宜これらの省略記法を用いることにする。
ここで注意しておくが、 あくまでこれは (メタ視点での) 省略記法であり、 プログラムの定義を拡張したわけではない。
ところで、 このプログラムは 0 番目のレジスタの値を 1 番目のレジスタに移すものであった。
このようなプログラムは大変便利なので、 名前をつけておくことにしよう。
より一般化して、 相異なる自然数 r,s に対して、 r 番目のレジスタの値を s 番目に移すプログラム
A: decr end incs backwardA
のことを、 以降は mover→s と書くことにする。
なお、 このプログラムは r 番目と s 番目以外のレジスタの値は一切変化させないことにも注目しておきたい。
では本題に移るが、 まずは初期関数が全て計算可能であることを示す。
命題 10.1.
原始再帰関数の初期関数 zero:0→, succ:1→, projik:k→(0≤i<k) は全て計算可能である。
証明.
各関数を計算するプログラムを構成すれば良い。
まず、 zero を計算するプログラムとは、 レジスタが (0,⋯) の状態で実行すると 0 番目のレジスタの値が 0 になるようなものであるが、 0 番目のレジスタは最初から 0 なので、 何もしないプログラムがこれに該当する。
すなわち、 zero は空の (長さ 0 の) プログラムによって計算されるから、 計算可能である。
succ を計算するプログラムとは、 任意の x∈ に対して、 レジスタが (x,0,⋯) の状態で実行すると 1 番目のレジスタの値が x+1 になるようなものである。
これを実現するには、 0 番目のレジスタの値を 1 番目に移した後に 1 番目のレジスタの値を 1 だけ増やせば良い。
したがって、 succ を計算するプログラムとして (move0→1,inc1) が考えられる。
よって、 succ は計算可能である。
projik(0≤i<k) を計算するプログラムとは、 任意の x∈k に対して、 レジスタが (x0,⋯,xk−1,0,⋯) の状態で実行すると k 番目のレジスタの値が xi になるようなものである。
これを実現するには、 i 番目のレジスタの値を k 番目に移せば良い。
したがって、 projik を計算するプログラムとして movei→k そのものが考えられる。
よって、 projik は計算可能である。
続いて、 計算可能性が合成で閉じていることを示したい。
そのためには、 合成前の関数のプログラムを使って合成後の関数のプログラムを構成すれば良い。
それを実現するための基本的なアイデアは合成前の関数のプログラムを逐次実行することであるが、 これには細かな問題がある。
例えば、 関数 f0,f1:→ と関数 g:2→ の合成 h:→ を考える。
f0,f1,g を計算するプログラムがそれぞれ 0,1, として与えられているとする。
さて、
h(x)=g(f0(x),f1(x))
であるわけだから、 これを計算したければ、 レジスタに入力された x に対して 0 と 1 を実行して f0(x),f1(x) を得て、 それに対してさらに を実行すれば良さそうである。
しかし、 これはナイーブにはうまくいかない。
レジスタを (x,0,⋯) で初期化して 0 を実行すると、 1 番目のレジスタの値は確かに f0(x) になるが、 それ以外のレジスタの値は保証されない。
そのため、 0 番目のレジスタがもはや x ではなくなっている可能性があり、 その場合この後で 1 を実行しても f1(x) は得られない。
さらに、 仮に 0 番目のレジスタが x のままであったとしても、 2 番目以降のレジスタに 0 以外の数値が残っている可能性もある。
1 はあくまでレジスタが (x,0,⋯) の状態で実行すると 1 番目のレジスタの値が f1(x) になることを保証しているだけなので、 2 番目以降のレジスタに 0 以外の値が格納されている場合にどのような結果になるかは分からない。
したがって、 プログラムをうまく合成するためには、 入力から特定の出力が得られること以上に、 特定の範囲のレジスタの値を一切変化させないことや、 入力以外のレジスタの値に動作が依存しないことなども保証されている必要がある。
また、 プログラムの入力と出力がそれぞれ 0 番目から k−1 番目までのレジスタと k 番目のレジスタに固定されているのも不便なので、 これも柔軟に変更できるようにしておきたい。
そこで、 プログラムが関数を計算することの定義を、 以下のように拡張する。
定義 10.2.
部分関数 f:k→ とプログラム をとる。
さらに、 相異なる自然数 r0,⋯,rk−1 および自然数 s,t をとる。
任意の x∈k に対して、 各 i(0≤i<k) に対して ri 番目のレジスタの値が xi である状態で を実行すると、 次の 2 条件がともに成り立つとする。
- f(x) が定義されているならば、 の実行後に s 番目のレジスタの値が f(x) になった状態で正常終了する。
さらに、 の実行中に 0 番目から t−1 番目までであって s 番目を除くレジスタの値は全て一切変化しない。
- f(x) が定義されていないならば、 の実行は永遠に終了しない。
このとき、 は r0,⋯,rk−1 から s へ t を保ちながら f を 「計算する (compute)」 という。
この定義の条件はなかなか厳しいが、 ある関数を通常の意味で計算するプログラムからは、 常に上記の条件を満たすプログラムを構成することができる。
これを示すために、 まずは便利なプログラムをいくつか用意しよう。
自然数 r に対し、 次のプログラムを考える。
A: decr end backwardA
これは、 r 番目のレジスタの値を減らし続けて、 それが 0 になったら終了するプログラムである。
つまり、 r 番目のレジスタの値を 0 にリセットするわけである。
このプログラムは、 以降 clearr と書くことにする。
また、 相異なる自然数 r,s,t に対し、 次のプログラムも考えよう。
clears mover→t A: dect end incr incs backwardA
先に言ってしまうとこれは、 r 番目のレジスタの値を s 番目のレジスタにコピーするプログラムである。
この際に、 t 番目のレジスタを作業領域として用いる。
プログラムの動きを順番に追ってみよう。
まず最初の 2 行で、 s 番目のレジスタを 0 にリセットし、 r 番目の値を一度 t 番目に移す。
この後の 5 行では、 この t 番目の値を減らしながら r 番目と s 番目の値を増やす。
これにより、 r 番目と s 番目の値が減らし始める前の t 番目の値と等しくなったところで、 t 番目の値が 0 になって終了する。
これで、 r 番目と s 番目の値がともに最初の r 番目の値と等しくなるので、 結果的に r 番目の値を s 番目にコピーしたことになる。
このプログラムは、 以降 copyr→s,t と書くことにする。
以上の準備のもと、 ある関数を計算するプログラムから定義 10.2 の条件を満たすプログラムを構成しよう。
命題 10.3.
部分関数 f:k→ とプログラム をとる。
さらに、 相異なる自然数 r0,⋯,rk−1 および自然数 s,t をとる。
が f を通常の意味で計算するならば、 あるプログラム [r0,⋯,rk−1→s∣t] が存在して、 これは r0,⋯,rk−1 から s へ t を保ちながら f を計算する。
証明.
まず、
m:=max{r∣ に incr もしくは decr が属する}
とおく。
レジスタの値を参照したり操作したりするのは inc 命令と dec 命令だけなので、 は m 番目以前のレジスタしか参照せず、 の動作は m 番目より後のレジスタの値には依存しない。
また、
w:=max(r0,⋯,rk−1,t)
とおき、 に属する inc 命令もしくは dec 命令が参照する全てのレジスタ番号に w を加えて得られるプログラムを +w と書くことにする。
すると、 +w は w 番目から w+m 番目までのレジスタしか参照しない。
したがって、 +w の動作は w+m 番目より後のレジスタの値には依存しないし、 +w の実行中に w 番目より前のレジスタの値が変化することはない。
ここで、 以下のプログラムを とする。
copyr0→w,w+1 copyr1→w+1,w+2 ⋮ copyrk−1→w+k−1,w+k clearw+k clearw+k+1 ⋮ clearw+max(m,k) +w movew+k→s
r0,⋯,rk−1 番目のレジスタの値がそれぞれ x0,⋯,xk−1 である状態から、 この の動作を追ってみよう。
まず、 これらのレジスタの値が w 番目から w+k−1 番目までに順にコピーされる。
すなわち、 w,⋯,w+k−1 番目のレジスタの値がそれぞれ x0,⋯,xk−1 になる。
続いて、 w+k 番目から w+max(m,k) 番目までのレジスタが 0 にリセットされる。
これにより、 レジスタ番号が w だけズレていることを除けば、 が f(x) を計算するときと同じ状況になっている。
そのため、 この後で +w が実行されると、 もし f(x) が定義されているのであれば、 これで w+k 番目のレジスタに f(x) が格納されるはずである。
最後に、 この w+k 番目のレジスタの値が s 番目のレジスタに移されるから、 s 番目のレジスタの値は f(x) になる。
また、 もし f(x) が定義されていないならば、 +w の実行は永遠に終了しないはずなので、 上記の も永遠に終了しない。
以上により、 この が定理で主張されている [r0,⋯,rk−1→s∣t] である。
この定理を利用すれば、 計算可能性が関数の合成で閉じていることが簡単に示せる。
命題 10.4.
部分関数 f0,⋯,fl−1:k→ および部分関数 g:l→ に対し、 これらから合成で得られる部分関数を h:k→ とする。
f0,⋯,fl−1,g が全て計算可能ならば、 h も計算可能である。
証明.
f0,⋯,fl−1,g を計算するプログラムをそれぞれ 0,⋯,l−1, とする。
このとき、 次のプログラムを とする。
0[0,⋯,k−1→k∣k] 1[0,⋯,k−1→k+1∣k+1] ⋮ l−1[0,⋯,k−1→k+l−1∣k+l−1] [k,⋯,k+l−1→k∣0]
レジスタが (x0,⋯,xk−1,0,⋯) である状態から の動作を追おう。
まず、 0[0,⋯,k−1→k∣k] が実行されると、 f0(x) が定義されているなら、 k 番目のレジスタにその f0(x) が格納される。
このとき、 k 番目より前のレジスタの値は変化しないから、 0,⋯,k−1 番目のレジスタの値は x0,⋯,xk−1 のままである。
したがって、 次に 1[0,⋯,k−1→k+1∣k+1] が実行されると、 f1(x) が定義されているなら、 k+1 番目のレジスタに f1(x) が格納される。
これを続けると、 l−1[0,⋯,k−1→k+l−1∣k+l−1] が実行された時点で、 f0(x),⋯,fl−1(x) が全て定義されているのであれば、 0,⋯,k−1,k,⋯,k+l−1 番目のレジスタの値はそれぞれ x0,⋯,xk−1,f0(x),⋯,fl−1(x) になっているはずである。
そのため、 ここで [k,⋯,k+l−1→k∣0] が実行されると、 g(f0(x),⋯,fl−1(x)) が定義されているなら、 k 番目のレジスタに g(f0(x),⋯,fl−1(x)) すなわち h(x) が格納される。
仮に f0(x),⋯,fl−1(x) のうちいずれかが定義されないなら、 それに対応する i[0,⋯,k−1→k+i−1∣k+i−1] の実行は終了しないので、 上記 の実行も終了しない。
これらが全て定義されていても g(f0(x),⋯,fl−1(x)) が定義されないなら、 [k,⋯,k+l−1→k∣0] の実行は終了せず、 やはり上記 の実行も終了しない。
以上により、 上記 は h を計算するプログラムの定義を満たしている。
したがって、 h は計算可能である。
次回は、 計算可能性が原始再帰と最小化でも閉じていることを示し、 全ての一般再帰関数が計算可能であることを示す。
参考文献
- H. B. Enderton (2011) 『Computability Theory』 Academic Press