日記 (2026 年 1 月 29 日)
前回は、 一般再帰関数が全て計算可能であることを示した。
今回は、 この逆、 すなわち計算可能関数が全て一般再帰的であることを示す。
この証明の方針は、 レジスタマシンの動作を全て一般再帰的関数で表現することである。
しかし、 一般再帰関数は自然数上の関数であるから、 そのためにはプログラムやメモリを自然数で表す必要があるので、 まずはその方法を整備しよう。
なお、 以降は自然数列の操作を各所で行うため、 必要であれば第 5 回を読み直して記号などを確認しておいてほしい。
初めに、 命令やプログラムを自然数にエンコードしよう。
このように形式機械のデータを自然数で表現したものは、 一般に 「Gödel 数」 と呼ばれている。
定義 12.1.
命令 c に対して自然数 ⌈c⌉ を、
⌈incr⌉ := ⟨0,r⟩ ⌈decr⌉ := ⟨1,r⟩ ⌈forwardq⌉ := ⟨2,q⟩ ⌈backwardq⌉ := ⟨3,q⟩
によって定義する。
これを c の 「Gödel 数 (— number)」 と呼ぶ。
定義 12.2.
プログラム =:(c0,⋯,cl−1) に対して自然数 ⌈⌉ を、
⌈⌉:=⟨⌈c0⌉,⋯,⌈cl−1⌉⟩
によって定義する。
これを の 「Gödel 数 (— number)」 と呼ぶ。
例えば、 プログラム
dec0 forward3 inc1 backward3
を とすると、 この Gödel 数 ⌈⌉ は、
⌈⌉ = ⟨⌈dec0⌉,⌈forward3⌉,⌈inc1⌉,⌈backward3⌉⟩ = ⟨⟨1,0⟩,⟨2,3⟩,⟨0,1⟩,⟨3,3⟩⟩ = ⟨22·31,23·34,21·32,24·34⟩ = ⟨12,648,18,1296⟩ = 213·3649·519·71297
となる。
見ての通り巨大な数になるが、 重要なのは数そのものではなく、 この数だけからプログラムの情報を完全に復元できる点である。
例えば、 の最初の命令の Gödel 数 ⌈dec0⌉ は、 ⌈⌉@0 として取得できる。
さらに、 この命令がどの種類なのか知りたければ、 ⌈⌉@0@0 を見てそれが 0 から 3 までのいずれであるかを確認すれば良い。
なお、 命令やプログラムの Gödel 数をとる操作は、 自然数への単射ではあるが全射にはなっていない。
例えば、 命令の Gödel 数の左成分は常に 3 以下なので、 ⟨4,0⟩=96 はどんな命令の Gödel 数にもなり得ない。
同じ理由で、 ⟨96⟩=297 はどんなプログラムの Gödel 数にもなり得ない。
ただし、 Gödel 数の全射性が必要になることはないので、 これは問題ではない。
さて、 これでプログラムを自然数にエンコードすることはできたので、 次にレジスタマシンの状況を自然数にエンコードしよう。
レジスタマシンの状況とはメモリとポインタのことであったが、 ポインタはそもそもただの自然数なので、 メモリをエンコードできれば良い。
そのメモリとは、 有限個を除いて 0 であるような自然数の列であった。
これのエンコーディングは、 有限列のエンコーディングと同様にして、 次のように素数の冪で定義することにする。
定義 12.3.
レジスタマシンのメモリ =:(xr)r∈ に対して自然数 ⌈⌉ を、
⌈⌉:=r∈pr(r)xr
によって定義する。
これを の 「Gödel 数 (— number)」 と呼ぶ。
有限列のエンコーディングとは異なり、 指数に 1 をたしていないことに注意してほしい。
メモリを構成する自然数は有限個を除いて 0 なので、 これによって上の積は実際には有限積になっており、 問題なく定義されることが保証されている。
メモリの Gödel 数から各レジスタの値を復元することも可能であり、 さらに言えばそれは原始再帰的に可能である。
命題 12.4.
原始再帰関数 @∗:2→ であって、 任意のメモリ (xr)r∈ と自然数 y に対し、
⌈(xr)r∈⌉@∗y=xy
を満たすものが存在する。
証明.
有限列の場合と同様に、 メモリの Gödel 数 ρ に対して、 pr(y)1, pr(y)2, ⋯ が順に ρ をわり切るか調べていけば良い。
したがって、
ρ@∗y:=μt<ρ.pr(y)t+1∤ρ
と定義すれば良い。
以上で、 レジスタマシンに関するデータを全て自然数にエンコードする方法が整った。
残る作業は、 このエンコーディングを用いてレジスタマシンの動作を一般再帰関数として表現することである。
とはいえ、 そのアイデアはほとんど第 9 回でレジスタマシンの厳密な形式化として述べた通りである。
すなわち、 命令による状況の変化を関数 next として表現し、 それを用いて特定のステップにおける状況を取得する関数 configat を定めるのである。
本題に入る前に、 1 つ便利な関数を定義しておこう。
命題 12.5.
次を満たす原始再帰関数 updateat:3→ が存在する。
メモリ と自然数 r,x に対し、 の r 番目のレジスタの値を x に更新したメモリを とすると、
updateat(⌈⌉,r,x)=⌈⌉
が成り立つ。
証明.
メモリの Gödel 数 ⌈⌉ において r 番目のレジスタの値は pr(r) の指数であるから、
updateat(ρ,r,x):=div(ρ,pr(r)ρ@∗r)·pr(r)x
とすれば良い。
これは原始再帰的である。
では、 next を原始再帰的に定義できることを示そう。
なお、 第 9 回のときと同様に、 定義上実行が終了している状態でもさらなる実行が可能であると見なし、 その場合はレジスタマシンの状況は変化しなかったものとする。
また、 以降の議論では、 実行が正常終了するか永遠に終了しないかのどちらかの場合のみを考えれば十分であるため、 議論を不要に複雑にしないためにも実行が異常終了する場合は考えないことにする。
命題 12.6.
次を満たす原始再帰関数 next:2→ が存在する。
任意のプログラム をとり、 レジスタマシンの状況が (,p) である状態で 1 ステップ実行した直後の状況を (,p) とする。
この 1 ステップの実行の前でも後でも異常終了していないのであれば、
next(⌈⌉,⟨⌈⌉,p⟩)=⟨⌈⌉,p⟩
が成り立つ。
証明.
φ:=⌈⌉ と κ:=⟨⌈⌉,p⟩ が与えられたとする。
式を見やすくするため、
ins(φ,p) := φ@p inskd(φ,p) := ins(φ,p)@0=φ@p@0 insarg(φ,p) := ins(φ,p)@1=φ@p@1
とおく。
すると、 ins(φ,p) とは状況 (,p) において参照される命令の Gödel 数であり、 inskd(φ,p) と insarg(φ,p) はそれぞれその命令の種類と引数である。
ins, insk, insa は 2 変数の関数として原始再帰的であることにも注目してほしい。
さらに、
mem(κ) := κ@0 ptr(κ) := κ@1 reg(κ,r) := mem(κ)@∗r=κ@0@∗r
とおけば、 mem(κ) と ptr(κ) とはそれぞれ の Gödel 数と p そのものである。
また、 reg(κ,r) とはこのときの r 番目のレジスタの値である。
mem, ptr, reg も 1 変数もしくは 2 変数の関数として原始再帰的である。
さて、 状況 (,p) において参照される命令が incr の形だったとする。
すなわち、 inskd(φ,ptr(κ))=0 の場合である。
この場合、 は の r 番目のレジスタの値を 1 増やしたものであり、 p は p+1 になる。
また、 この r は insarg(φ,ptr(κ)) として取得できる。
簡単のため、
insat(φ,κ):=insarg(φ,ptr(κ))
と書くことにすれば、 と p はそれぞれ φ と κ だけを用いて、
⌈⌉ = updateat(mem(κ),insat(φ,κ),reg(κ,insat(φ,κ))+1) p = ptr(κ)+1
と表せる。
この式の右辺には原始再帰的な演算しか行っていないことに注目したい。
続いて、 参照される命令が decr の形の場合、 すなわち inskd(φ,ptr(κ))=1 の場合を考える。
この場合は、 r 番目のレジスタの値によりさらに場合分けされる。
r 番目のレジスタの値が 0 のとき、 すなわち reg(κ,insat(φ,κ))=0 のときは、 メモリは変化せずにポインタが 1 個進むので、
⌈⌉ = mem(κ) p = ptr(κ)+1
である。
r 番目のレジスタが正のとき、 すなわち reg(κ,insat(φ,κ))>0 のときは、 そのレジスタの値が 1 減ってポインタは 2 個進むので、
⌈⌉ = updateat(mem(κ),insat(φ,κ),reg(κ,insat(φ,κ))∸1) p = ptr(κ)+2
となる。
次に、 参照される命令が forwardq の形の場合、 すなわち inskd(φ,ptr(κ))=3 の場合を考える。
この場合は、 レジスタの値は変化せず、 ポインタだけが q 個進む。
したがって、
⌈⌉ = mem(κ) p = ptr(κ)+insarg(φ,ptr(κ))
と書ける。
最後に、 参照される命令が backwardq の形の場合、 すなわち inskd(φ,ptr(κ))=4 の場合を考える。
この場合は、 ポインタだけが q 個戻る。
したがって、
⌈⌉ = mem(κ) p = ptr(κ)∸insarg(φ,ptr(κ))
と書ける。
2 つ目の式の右辺では結果を自然数に収めるために切り捨て減法を用いているので、 ptr(κ)<insarg(φ,ptr(κ)) である場合は結果は一律 0 になってしまう。
しかし、 ptr(κ)<insarg(φ,ptr(κ)) であるとはポインタが 0 未満になって異常終了する場合であり、 ここでは異常終了を考える必要はないので、 問題にはならない。
以上の考察により、 next は、
next(φ,κ):={ ⟨ updateat(mem(κ),insat(φ,κ),reg(κ,insat(φ,κ))+1) ptr(κ)+1⟨ (inskd(φ,ptr(κ))=0) ⟨ mem(κ) ptr(κ)+1⟨ (inskd(φ,ptr(κ))=1,reg(κ,insat(φ,κ))=0) ⟨ updateat(mem(κ),insat(φ,κ),reg(κ,insat(φ,κ))∸1) ptr(κ)+2⟨ (inskd(φ,ptr(κ))=1,reg(κ,insat(φ,κ))>0) ⟨ mem(κ) ptr(κ)+insarg(φ,ptr(κ))⟨ (inskd(φ,ptr(κ))=2) ⟨ mem(κ) ptr(κ)∸insarg(φ,ptr(κ))⟨ (inskd(φ,ptr(κ))=3) ⟨ mem(κ) ptr(κ)⟨ (上記以外)
と定めれば良い。
これは原始再帰的である。
次に、 configat も原始再帰的に書けることを示すが、 これは第 9 回で述べた形式化と全く同じようにすれば良いだけである。
命題 12.7.
次を満たす原始再帰関数 configat:3→ が存在する。
任意のプログラム をとり、 初期のメモリが である状態から n ステップ実行した直後のレジスタマシンの状況を (n,pn) とする。
この途中で異常終了していないのであれば、
configat(⌈⌉,⌈⌉,n)=⟨⌈n⌉,pn⟩
が成り立つ。
証明.
原始再帰を用いて、
configat(φ,ρ,0) = ⟨ρ,0⟩ configat(φ,ρ,n+1) = next(φ,configat(φ,ρ,n))
とすれば良い。
この右辺には原始再帰的な演算しか表れていないので、 これで定義される configat も原始再帰的である。
これらを用いれば、 プログラムを実行した結果得られる出力も関数として書くことができ、 しかもそれを一般再帰的に定義できることが分かる。
やはり方針は第 9 回の形式化と同様である。
命題 12.8.
次を満たす一般再帰関数 run(k):k+1→ が存在する。
任意のプログラム をとり、 自然数列 x∈k に対して初期のメモリが (x0,⋯,xk−1,0,⋯) である状態でこれを実行したとすると、 以下がともに成り立つ。
- 実行が正常終了するならば、 そのときの k 番目のレジスタの値が y とすると、 run(k)(⌈⌉,x)=y が成り立つ。
- 実行が永遠に終了しないならば、 run(k)(⌈⌉,x) は定義されない。
この命題が存在を主張する run(k) は、 もちろん k に依存するため、 ここでは上付き添字として k を附して記した。
ただし以降では、 文脈から明らかな場合はこの k を省略することにする。
変数の個数 k に依存する名前の付いた関数は今後もいくつか登場するが、 それについても同様に添字は省略することがある。
証明.
まず、 プログラム を初期のメモリが である状態から実行したときに、 正常終了するステップ数を取得することを考えよう。
正常終了するとはポインタがプログラムの長さに一致することだったので、 φ:=⌈⌉ と ρ:=⌈⌉ が与えられたとき、 正常終了するステップ数を n∞(φ,ρ) とすると、
n∞(φ,ρ)=μn.configat(φ,ρ,n)@1=len(φ)
が成り立つ。
この n∞ は 2 変数の関数として一般再帰的である。
さて、 自然数列 x に対して、 メモリ (x0,⋯,xk−1,0,⋯) の Gödel 数を tomem(x) と書くことにすれば、 これは、
tomem(x)=pr(0)x0·⋯·pr(k−1)xk−1
と書ける。
これは k 変数の関数として原始再帰的である。
さて、 命題の主張通りに を実行したとしてそれが正常終了したとする。
φ:=⌈⌉ とおくと、 正常終了時のステップ数は n∞(φ,tomem(x)) である。
このときの状況は configat(φ,tomem(x),n∞(φ,tomem(x))) であるから、 その k 番目のレジスタの値は、
configat(φ,tomem(x),n∞(φ,tomem(x)))@0@∗k
である。
また、 実行が永遠に終了しないのであれば、 n∞(φ,tomem(x)) が定義されないので、 上の式全体も定義されない。
ということは、 どちらの場合であろうと、
run(φ,x):=configat(φ,tomem(x),n∞(φ,tomem(x)))@0@∗k
と定義すれば良いということである。
これは k+1 変数の関数として一般再帰的である。
さて、 当初の目的は計算可能関数が全て一般再帰的であることを示すことであったが、 それは上の命題からすぐに分かる。
定理 12.9.
部分関数 f:k→ に対し、 f が計算可能ならば、 f は一般再帰的である。
証明.
f が計算可能であれば、 それを計算するプログラム が存在する。
ここで、 部分関数 f:k→ を f(x):=run(⌈⌉,x) によって定めると、 命題 12.8 より run は一般再帰的なので、 f も一般再帰的である。
さらに、 命題 12.8 で述べられている run の性質は、 まさに が f を計算することを述べている。
すなわち f=f であるから、 f は一般再帰的である。
定理 12.10.
部分関数 f:k→ に対し、 f が一般再帰的であることと f が計算可能であることは同値である。
これにより、 一般再帰性と計算可能性は、 定義の方針は異なるものの全く同じ性質であることが分かった。
「計算できる」 ことを定式化するための別々のアプローチが結局同じものに行き着いたわけなので、 この性質こそが、 我々が直感的に 「計算できる」 と思える関数の正しい定式化だと言えるだろう。
参考文献
- H. B. Enderton (2011) 『Computability Theory』 Academic Press