日記 (2026 年 2 月 3 日)
前回までで、 関数の一般再帰性と計算可能性が実は全く同じ性質であったことが分かった。
今回は、 前回の結果を踏まえて、 列挙定理と停止性問題という 2 つのトピックについて触れる。
なお、 一般再帰性と計算可能性は同じ意味なので、 以降でこの性質を指すときは 「計算可能」 という用語に統一することにする。
また、 計算可能関数とプログラムも適宜同一視する。
定理 13.1 [列挙定理 (enumeration theorem)].
次を満たす計算可能関数 apply(k):k+1→ が存在する。
任意の計算可能関数 f:k→ に対し、 ある自然数 e∈ が存在して、 任意の自然数列 x∈k に対し、
apply(k)(e,x)=f(x)
が成り立つ。
証明.
この定理はほとんど命題 12.8 の言い換えである。
実際、 この定理が存在を主張している apply とは、 命題 12.8 の run そのものである。
そのことを以下に示そう。
任意に計算可能関数 f をとると、 それを計算するプログラム が存在するので、 e:=⌈⌉ とおく。
すると、 命題 12.8 の主張とは、 任意の x∈k に対して run(e,x)=f(x) が成り立つということである。
つまり、 この run は、 まさに上記定理が主張している apply が満たすべき性質を満たしている。
この定理の主張は、 全ての計算可能関数 f に対して、 その関数の 「番号」 と呼べるべき自然数 e を割り当てることができ、 その番号 e と引数 x を渡すとその関数の値 f(x) を何でも計算してくれる計算可能関数 apply が存在するということである。
つまり、 関数とその番号を同一視してしまえば、 この定理は、 関数と引数からその値を計算する行為そのものも計算可能であると述べていることになる。
以降の議論で便利なため、 番号 e に対応する関数を ⟦e⟧ と書くことにしよう。
定義 13.2.
自然数 e∈ に対し、 部分関数 ⟦e⟧(k):k→ を、
⟦e⟧(k)(x):=apply(k)(e,x)
によって定義する。
列挙定理の系として、 計算可能関数を以下のように順番に取得できることが分かる。
これが、 列挙定理が 「列挙定理」 と呼ばれている所以である。
定理 13.3.
集合
{⟦0⟧(k),⟦1⟧(k),⟦2⟧(k),⋯}
は k 変数の計算可能関数全体の集合に一致する。
証明.
上記の集合を S とおく。
任意に S の元 ⟦e⟧ をとると、 これは計算可能関数 apply の最初の引数を固定しただけのものだから計算可能である。
逆に、 任意に計算可能関数 f をとると、 定理 13.1 によってある番号 e が存在して f=⟦e⟧ が成り立つから、 f は S に属する。
注意すべき点として、 関数 f に対して f=⟦e⟧ が成り立つような番号 e が一意であることまでは保証されていない。
これまでの議論を追えば、 関数の番号というのは結局はその関数を計算するプログラムの Gödel 数であるわけだが、 1 つの関数を計算するプログラムが 1 つしかないわけではない。
実際、 プログラムの適当な位置に forward1 を挿入してもプログラムの実行にはほとんど影響がないため、 同じ関数を計算するプログラムは無数に作れる。
したがって、 上の定理の ⟦0⟧,⟦1⟧,⋯ という列には、 計算可能関数が全て含まれてはいるが、 重複がある可能性もある。
さて、 計算可能関数を番号付けできたということは、 特に 1 変数の計算可能関数について、 縦軸と横軸にそれぞれ関数の番号とその関数の値を記した 2 次元の表
⟦0⟧(0) ⟦0⟧(1) ⟦0⟧(2) ⋯ ⟦1⟧(0) ⟦1⟧(1) ⟦1⟧(2) ⋯ ⟦2⟧(0) ⟦2⟧(1) ⟦2⟧(2) ⋯ ⋮ ⋮ ⋮ ⋱
が得られたということである。
しかも定理 13.1 によって、 この表の x 行 y 列にある成分 ⟦x⟧(y) すなわち apply(x,y) は計算可能である。
ここで、 この表に対して対角線論法を適用してみよう。
この表の対角線に書かれた値に 1 を加えた値を得る関数
δ(x) := ⟦x⟧(x)+1 = apply(x,x)+1
も作ると、 これは計算可能である。
したがって、 この関数自身も上の表のどこかの行として現れているはずである。
すなわち、 δ=⟦e⟧ となる番号 e が存在するはずである。
すると、
⟦e⟧(e)=δ(e)=⟦e⟧(e)+1
が成り立つので、 何かがおかしい。
…なんてことはなく、 関数の値は定義されないことがあるので、 ⟦e⟧(e) が定義されなければ上の式は両辺定義されない状態で成立する。
しかし、 この δ を拡張するような全域な計算可能関数があったとしたら、 それは矛盾を生じる。
このことを多変数の場合に一般化して改めて述べておこう。
命題 13.4.
部分関数 δ:k→ を、
δ(x) := ⟦x0⟧(k)(x0,⋯,xk−1)+1 = apply(k)(x0,x0,⋯,xk−1)+1
で定義する。
これを拡張する全域な計算可能関数は存在しない。
証明.
そのような全域な計算可能関数 f が存在したとする。
すると定理 13.1 により、 ある番号 e が存在して f=⟦e⟧ が成り立つ。
ここで、 f は全域だから f(e,⋯,e) は必ず定義され、 さらに f は δ の拡張だから、
f(e,⋯,e)=δ(e,⋯,e)=⟦e⟧(e,⋯,e)+1
が成り立ち、 特に ⟦e⟧(e,⋯,e) は定義される。
一方で f=⟦e⟧ であるから、
f(e,⋯,e)=⟦e⟧(e,⋯,e)
も成り立つ。
すなわち ⟦e⟧(e,⋯,e)=⟦e⟧(e,⋯,e)+1 を得るが、 この両辺とも定義された値であるから、 これは矛盾である。
したがって、 命題の主張を満たす全域な計算可能関数は存在しない。
この事実から分かることとして、 関数の値が定義されるかされないかを判定することは計算可能ではない。
プログラムの見方で言い換えれば、 プログラムの実行が終了するかしないかを判定することは計算可能ではない。
この 「プログラムの実行が終了するかどうかを判定するプログラムが存在するか」 という問題は 「停止性問題」 と呼ばれており、 次に示すようにこれは否定的に解決された。
定理 13.5 [停止性問題の計算不可能性 (uncomputability of halting problem)].
関係 Halt(k)⊆k+1 を
(w,x)∈Halt(k):⟺⟦w⟧(k)(x)↓
で定めると、 これは計算可能ではない。
証明.
Halt が計算可能であったと仮定する。
部分関数 f:k→ を、
f(x):={ apply(x0,x0,⋯,xk−1)+1 ((x0,x)∈Halt) 0 ((x0,x)∉Halt)
で定めると、 仮定から Halt は計算可能であり定理 13.1 から apply も計算可能なので、 この f も計算可能である。
また、 Halt の定義によって (x0,x)∈Halt であれば ⟦x0⟧(x) すなわち apply(x0,x) が定義されるから、 この f は全域である。
さらに、 この f は命題 13.4 の δ の拡張にもなっている。
このような f の存在は命題 13.4 に矛盾するから、 Halt は計算可能ではあり得ない。
この事実から特に、 ある計算可能関数を定義しようとしたときに、 別の計算可能関数の値が定義されるかされないかによって場合分けすることはできないことになる。
このことは、 後で扱う計算可枚挙性の議論で重要になる。
参考文献
- H. B. Enderton (2011) 『Computability Theory』 Academic Press