日記 (2025 年 12 月 30 日)
前回まででは、 原始再帰関数の広い表現力を見つつ、 その限界にも触れた。
そのため、 「計算できる」 関数のクラスとしては原始再帰関数のクラスは不十分であると言える。
今回は、 直感的に 「計算できる」 関数が全て含まれるより広い関数のクラスの候補として、 一般再帰関数を導入する。
定理 4.3 で示したように、 有界な最小化 (関係を満たす数を探す演算) であれば原始再帰性は保存される。
したがって、 たとえ与えられた関係を満たす数が存在することが事前に分かっていたとしても、 それを探索する上界を前もって与えられなければ、 原始再帰的な範囲でその数を取得することはできない。
この有界性が原始再帰関数の表現力の限界とも言えるだろう。
そこで、 有界でないかもしれない最小化演算を許すことにしたのが一般再帰関数である。
有界でないかもしれない最小化演算は、 次のように定義される。
定義 7.1.
関係 P⊆k+1 をとる。
数 x∈k に対して、 定義されないかもしれない数 μt.P(x,t) を
μt.P(x,t):={ min{t∣P(x,t)} (∃tP(x,t)) ↑ (上記以外)
で定義する。
この μ は 「最小化演算子 (minimization operator)」 と呼ばれる。
定義 7.2.
関係 P⊆k+1 をとる。
部分関数 h:k→ が、 任意の x∈k に対して、
h(x):=μt.P(x,t)
を満たすとき、 h は P から 「最小化 (minimization)」 で得られるという。
最小化演算子は、 与えられた関係を満たす数を 0 から探していって見つかったものを返すが、 そもそもそのような数が存在しなかったら未定義となる。
そのため、 最小化で得られる関数は全域でない真の部分関数になる可能性がある。
これを用いて、 一般再帰関数を次のように定義する。
定義 7.3.
部分関数が 「一般再帰的 (general recursive)」 であることを、 以下によって帰納的に定義する。
- 初期関数 zero, succ, projik(0≤i<k) は一般再帰的である。
- 部分関数 f0,⋯,fl−1:k→ および部分関数 g:l→ が全て一般再帰的ならば、 これらから合成で得られる部分関数 h:k→ も一般再帰的である。
- 部分関数 f:k→ および部分関数 g:k+2→ がともに一般再帰的ならば、 これらから原始再帰で得られる部分関数 h:k+1→ も一般再帰的である。
- 関係 P⊆k+1 が一般再帰的ならば、 これらから最小化で得られる部分関数 h:k→ も一般再帰的である。
一般再帰性の定義には (有界でない) 最小化が含まれているので、 一般再帰関数は全域にならない可能性がある。
このことは常に注意すべきである。
例えば、 部分関数 f:k→ と g:k+2→ から原始再帰で関数 h:k+1→ を作ったとする。
つまりこの h は、
h(x,0) = f(x) h(x,y+1) = g(x,y,h(x,y))
と書ける。
ここで、 例えばある x に対して f(x) が定義されなかったとしよう。
すると、 それに等しい h(x,0) も定義されないし、 そのせいで h(x,1)=g(x,0,h(x,0)) も定義されず、 結局全ての y に対して h(x,y) は定義されないことになる。
さて、 一般再帰関数についてすぐ分かることとして、 原始再帰関数は全て一般再帰的である。
したがって、 例えば加算や乗算などの原始再帰的であることが分かっている演算は、 全て一般再帰的でもある。
定理 7.4.
部分関数 f:k→ に対し、 f が原始再帰的ならば、 f は一般再帰的でもある。
前回までで原始再帰的な関数や関係から新しい原始再帰的な関数や関係を作る操作をいくつか見たが、 同じ操作が一般再帰性も保つことを証明しよう。
命題 7.5.
部分関数 f:k+1→ に対し、 部分関数 Σf:k+1→ および Πf:k+1→ を
Σf(x,y) := t<yf(x,t)=f(x,0)+⋯+f(x,y−1) Πf(x,y) := t<yf(x,t)=f(x,0)×⋯×f(x,y−1)
で定める。
f が一般再帰的ならば、 Σf と Πf も一般再帰的である。
命題 7.6.
関係 P,Q⊆k をとる。
P と Q がともに一般再帰的ならば、 ∁P も P∩Q も P∪Q も全て一般再帰的である。
命題 7.7.
関係 P⊆k+1 に対し、 関係 ∀P,∃P⊆k+1 を
(x,y)∈∀P :⟺ ∀t<yP(x,t) (x,y)∈∃P :⟺ ∃t<yP(x,t)
で定める。
P が一般再帰的ならば、 ∀P と ∃P も一般再帰的である。
なお、 有界でない量化が一般再帰性を保つとは限らない。
すなわち、 関係 P⊆k+1 に対して、 関係 ∀P,∃P⊆k を
x∈∀P :⟺ ∀tP(x,t) x∈∃P :⟺ ∃tP(x,t)
で定めたとき、 P が一般再帰的であっても、 ∀P や ∃P が一般再帰的になるとは限らない。
有界でない最小化が可能なのに有界でない量化ができないのは一見直感に反するかもしれないが、 このことは少し証明を試みてみると分かる。
試しに、 P が一般再帰的であるとして ∃P が一般再帰的であることを示そうとしてみよう。
そのためには、 ch∃P が一般再帰的であることを示す必要がある。
しかし、 最小化を用いてできるのは、
f(x) := sgn((μt.P(x,t))+1) = { 1 (∃tP(x,t)) ↑ (上記以外)
という関数を作るところまでである。
これは、 x に対して P(x,t) を満たす t が存在しないときに 0 を返すことができていないので、 ch∃P とは等しくない。
この違いは、 後で計算可能性と計算可枚挙性の違いとして定式化する。
一般再帰性を保つ操作についての話に戻ろう。
次は場合分けによる関数の定義についてである。
命題 7.8.
部分関数 f,g:k→ および関係 P⊆k に対し、 部分関数 h:k→ を
h(x):={ f(x) (x∈P) g(x) (x∉P)
で定める。
f,g,P が全て一般再帰的であれば、 h も一般再帰的である。
この証明は、 命題 4.1 の証明そのままというわけにはいかない。
命題 4.1 の証明では、 h が
h(x)=f(x)chP(x)+g(x)ch∁P(x)
と書けるとして話を進めたが、 今回の状況ではこれは正しくない。
なぜなら、 f(x)chP(x)+g(x)ch∁P(x) という式は、 f(x) と g(x) がともに定義されているときに限り全体が定義されるが、 一方で、
{ f(x) (x∈P) g(x) (x∉P)
という式は、 例えば x∈P でありさえすれば f(x) だけが定義されていれば全体も定義されるからである。
このように、 両者は定義域が異なる可能性があるのである。
そのため、 上記の命題の証明には若干の工夫が要る。
証明.
まず、 部分関数 f:k+1→ を
f(x,0) = 0 f(x,y+1) = f(x)
という原始再帰により定義すると、 仮定から f は一般再帰的なので、 この f も一般再帰的である。
これを用いて、 部分関数 fP:k→ を
fP(x):=f(x,chP(x))
で定めれば、 仮定から P は一般再帰的なので、 この fP も一般再帰的である。
すると、 この fP は、
fP(x)={ f(x) (x∈P) 0 (x∉P)
と書ける。
同様にして g∁P:k→ を定めれば、 h は
h(x)=fP(x)+g∁P(x)
と書ける。
fP と g∁P も一般再帰的なので、 h も一般再帰的である。
以上により、 第 4 回の最後に挙げた操作は全て一般再帰性も保つことが分かった。
これに加えて有界とは限らない最小化も一般再帰的な範囲で可能で、 その分だけ一般再帰関数の方が表現力が高くなっている。
次回は、 第 6 回で紹介した Ackermann 関数が一般再帰関数にはなっていることを示す予定である。
参考文献
- H. B. Enderton (2011) 『Computability Theory』 Academic Press