日記 (2026 年 2 月 26 日)
第 13 回は、 計算可能でない関係の例として停止性問題を挙げた。
すなわち、 関係 Halt(k)⊆k+1 を
(w,x)∈Halt(k):⟺⟦w⟧(k)(x)↓
で定めると、 これは計算可能ではないのであった。
ところで、 これが計算可能でないというのは、 その特性関数
chHalt(k)(w,x):={ 1 (⟦w⟧(k)(x)↓) 0 (⟦w⟧(k)(x)↑)
が計算可能でないということである。
つまり、 関数の番号 w とそれに渡す引数 x を渡したときに、 ⟦w⟧(x) が定義されるかされないかに応じて 1 か 0 のどちらかを必ず返す計算可能関数は存在しないということである。
しかし、 この条件を少し緩めて、 ⟦w⟧(x) が定義されるなら 1 を返すという条件だけを満たす計算可能関数であれば存在する。
実際、 関数 f:k+1→ を
f(w,x):=apply(k)(w,x)·0+1
と定めれば、 apply が計算可能であることからこの f も計算可能であり、 ⟦w⟧(x) が定義されるなら f(w,x) も定義されてその値は常に 1 である。
一方で、 ⟦w⟧(x) が定義されなければ f(w,x) も定義されない。
すなわち、 この f は、
f(w,x)={ 1 (⟦w⟧(k)(x)↓) ↑ (⟦w⟧(k)(x)↑)
を満たす。
chHalt とこの f の違いは非常に重要である。
これはプログラムの見方をすると分かりやすい。
chHalt を計算するプログラムは (もしあったとしたら) 必ず停止するので、 このプログラムを走らせて結果が出ていなければ、 それは確実にまだ計算途中であるということになる。
したがって、 結果が出るまでもう少し待とうという判断ができる。
しかし一方で、 f を計算するプログラムはそもそも停止しないことがあるので、 引数 (w,x) を渡して走らせているときに、 ⟦w⟧(x) が定義されてはいるが単に計算途中であるだけなのか ⟦w⟧(x) が定義されておらず永遠に停止しないのかは分からない。
そのため、 結果が出ると信じてさらに待つべきなのか、 これは永遠に停止しないと考えて実行を中断すべきなのか、 判断しづらい。
今述べた停止性問題のように、 真偽に応じて 1 か 0 を必ず返す関数は計算可能にならないものの、 真のときだけ 1 を返す関数であれば計算可能になるような関係は多く存在する。
そこで、 これを定式化して名前をつけておこう。
定義 15.1.
関係 P⊆k に対して、 部分関数 schP:k→ を
schP(x):={ 1 (x∈P) ↑ (x∉P)
で定義する。
これを P の 「半特性関数 (semicharacteristic function)」 という。
定義 15.2.
関係 P⊆k に対し、 P の半特性関数が計算可能であるとき、 P は 「計算可枚挙 (computably enumerable)」 であるという。
この用語を使えば、 停止性問題は計算可能ではないが計算可枚挙ではあると言える。
さてここからは、 計算可枚挙性についてより深く考察していくことにする。
まず明らかに分かることとして、 計算可能であれば計算可枚挙でもある。
定理 15.3.
関係 P⊆k に対し、 P が計算可能ならば、 P は計算可枚挙でもある。
証明.
P の半特性関数は、
schP(x)={ 1 (x∈P) ↑ (x∉P)
であった。
どんな引数に対しても値が定義されない部分関数は計算可能であるから、 P が計算可能であれば、 上の式は計算可能関係による計算可能関数の場合分けである。
すなわち、 この schP は計算可能であることになり、 つまり P は計算可枚挙である。
続いて、 計算可枚挙性の特徴付けをいくつか挙げよう。
まず、 計算可枚挙性は計算可能関数の定義域として書けることが分かる。
定理 15.4.
関係 P⊆k に対し、 以下の 2 条件は同値である。
- P は計算可枚挙である。
- ある計算可能関数 f:k→ が存在して、 P=dom(f) が成り立つ。
証明.
条件 1 ⇒ 条件 2:P が計算可枚挙であれば、 schP は計算可能であり、 半特性関数の定義から P=dom(schP) である。
条件 2 ⇒ 条件 1:条件の通りの f をとると、 schP は schP(x)=f(x)·0+1 と書ける。
したがって、 この schP は計算可能であり、 P は計算可枚挙である。
定理 13.3 で述べたように、 k 変数の計算可能関数全体は
{⟦0⟧(k),⟦1⟧(k),⟦2⟧(k),⋯}
と列挙できたことを思い出すと、 これによって k 変数の計算可枚挙関係も
{dom(⟦0⟧(k)),dom(⟦1⟧(k)),dom(⟦2⟧(k)),⋯}
と列挙できることになる。
さて、 計算可枚挙性は以下のようにも特徴付けすることができる。
定理 15.5.
関係 P⊆k に対し、 以下の 2 条件は同値である。
- P は計算可枚挙である。
- ある原始再帰的関係 Q⊆k+1 が存在して、 任意の x∈k に対し、
x∈P⟺∃t∈(x,t)∈Q
が成り立つ。
- ある自然数 m∈ と原始再帰的関係 Q⊆k+m が存在して、 任意の x∈k に対し、
x∈P⟺∃t∈m(x,t)∈Q
が成り立つ。
- ある自然数 m∈ と計算可能関係 Q⊆k+m が存在して、 任意の x∈k に対し、
x∈P⟺∃t∈m(x,t)∈Q
が成り立つ。
証明.
条件 1 ⇒ 条件 2:仮定から schP は計算可能である。
したがって定理 14.2 により、 ある自然数 e∈ が存在して、 schP は
schP(x)=ext(μt.Haltat(e,x,t))
と書ける。
ここで、 ext は原始再帰的だから特に全域なので、 schP(x) が定義される必要十分条件は μt.Haltat(e,x,t) が定義されることであり、 それは Haltat(e,x,t) を満たす t が存在することと同値である。
したがって、 Q⊆k+1 を
Q(x,t):⟺Haltat(e,x,t)
で定めれば、 定理 14.2 によってこれは原始再帰的であって、
P(x) ⟺ schP(x)↓ ⟺ ∃tHaltat(e,x,t) ⟺ ∃tQ(x,t)
が成り立つ。
条件 2 ⇒ 条件 3:条件 2 とは条件 3 において m=1 とした場合であるから、 これは明らかである。
条件 3 ⇒ 条件 4:原始再帰的関係は計算可能だから、 これは明らかである。
条件 4 ⇒ 条件 1:条件の通りの m と Q をとり、 部分関数 f:k→ を、
f(x):=μτ.Q(x,τ@0,⋯,τ@(m−1))
で定める。
仮定から Q は計算可能だから、 この f も計算可能である。
さらに、 自然数列のエンコーディングの性質により、
f(x)↓ ⟺ ∃τ∈Q(x,τ@0,⋯,τ@(m−1)) ⟺ ∃t∈mQ(x,t0,⋯,tm−1) ⟺ P(x)
が成り立つ。
そのため schP は、
schP(x)=f(x)·0+1
と書けるから、 schP は計算可能であり、 P は計算可枚挙である。
最後に今度は、 計算可枚挙性を用いた計算可能性の特徴付けも見ておこう。
定理 15.6.
関係 P⊆k に対し、 以下の 2 条件は同値である。
- P は計算可能である。
- P と ∁P はともに計算可枚挙である。
証明.
条件 1 ⇒ 条件 2:P が計算可能であれば、 ∁P も計算可能である。
したがって定理 15.3 により、 P と ∁P はともに計算可枚挙でもある。
条件 2 ⇒ 条件 1:P と ∁P がともに計算可枚挙なら、 定理 15.6 によって、 ある原始再帰的関係 Q,Q⊆k+1 が存在して、
x∈P ⟺ ∃t(x,t)∈Q x∉P ⟺ ∃t(x,t)∈Q
と書ける。
すると、 どんな x∈k に対しても、 (x,t)∈Q もしくは (x,t)∈Q のどちらか一方を満たす t が必ず存在する。
そこで、 関数 f:k→ を、
f(x):=μt.((x,τ)∈QOR(x,τ)∈Q)
で定めると、 この f は全域になる。
さらに、 Q と Q が原始再帰的であることから、 f は計算可能でもある。
また、 この定義から、
x∈P⟺(x,f(x))∈Q
が成り立つが、 これはつまり、
chP(x)=chQ(x,f(x))
が成り立つということである。
この右辺に現れている f と Q はともに (全域かつ) 計算可能だから、 これで chP が計算可能であること、 すなわち P が計算可能であることが示された。
上記の条件 2 から条件 1 を導く証明では、 Q の存在により f を全域にできるところが本質的である。
もし ∁P が計算可枚挙とは限らず Q の存在が保証されなかったならば、 f(x):=μt.(x,τ)∈Q にように f を定めてもこれが全域になるとは限らない。
そのため、 chQ(x,f(x)) も全域とは限らず、 特に x∉P のときにきちんと 0 を返せるとは限らない。
次回は、 関係の計算可枚挙性と計算可能関数の値域との関係性を見ることにする。
参考文献
- H. B. Enderton (2011) 『Computability Theory』 Academic Press