日記 (2025 年 12 月 25 日)
今回は、 原始再帰的な範囲で可能なことをさらに見ていく。
関数を場合分けによって定義することはよくあるが、 場合分けの条件が原始再帰的であれば原始再帰性は保たれる。
命題 4.1.
部分関数 f,g:k→ および関係 P⊆k に対し、 部分関数 h:k→ を
h(x):={ f(x) (x∈P) g(x) (x∉P)
で定める。
f,g,P が全て原始再帰的であれば、 h も原始再帰的である。
証明.
h は、
h(x)=f(x)·chP(x)+g(x)·ch∁P(x)
と書ける。
f,g,P が全て原始再帰的であると仮定すれば、 まず定理 3.3 により ∁P も原始再帰的である。
また、 命題 2.7 と命題 2.8 より加法と乗法も原始再帰的である。
したがって、 これらの合成で書けた h も原始再帰的である。
この定理を何度も使うことで、 2 つ以上の場合分けも原始再帰性を保つことが分かる。
例えば、 部分関数 f1,f2,f3,g:k→ および関係 P1,P2,P3⊆k に対して、 部分関数 h:k→ を
h(x):={ f1(x) (x∈P1) f2(x) (x∉P1ANDx∈P2) f3(x) (x∉P1ANDx∉P2ANDx∈P3) g(x) (x∉P1ANDx∉P2ANDx∉P3)
で定めれば、 f1,f2,f3,g,P1,P2,P3 が全て原始再帰的なら h も原始再帰的になる。
続いて、 有界最小化演算子を導入しよう。
これは、 与えられた関係を満たす数を探し出す演算子である。
定義 4.2.
関係 P⊆k+1 をとる。
数 x∈k および y∈ に対して、 数 μt<y.P(x,t) を
μt<y.P(x,t):={ min{t∣P(x,t)} (∃t<yP(x,t)) y (上記以外)
で定義する。
この μ は 「有界最小化演算子 (bounded minimization operator)」 と呼ばれる。
つまり、 μt<y.P(x,t) とは、 t を 0 から順に増やしながら P(x,t) が成り立つか調べていき、 それが始めて成り立ったときの t のことである。
ただし、 t を y−1 まで増やしても P(x,t) が成り立たなかったら、 探索を諦めて y を返す。
有界最小化演算は原始再帰性を保存する。
定理 4.3.
関係 P⊆k+1 に対し、 部分関数 h:k+1→ を
h(x,y):=μt<y.P(x,t)
で定める。
P が原始再帰的であれば、 h も原始再帰的である。
証明.
h(x,y) を原始再帰の形で書くことを目標とする。
まず、 定義から明らかに h(x,0)=0 である。
そこで次に、 h(x,y+1) を x, y, h(x,y) の式で表すことを考える。
もし P(x,t) を満たす t が y 未満に存在するならば、 そのような t のうち最小のものが h(x,y) である。
すると、 P(x,t) を満たす y+1 未満の t のうち最小のものも、 当然 h(x,y) である。
すなわち、 この場合は h(x,y+1)=h(x,y) となる。
P(x,t) を満たす t が y 未満に存在しない場合は、 P(x,y) が成り立つかが問題になる。
もし P(x,y) が成り立つなら、 P(x,t) を満たす y+1 未満の t で最小なものは y になるため、 h(x,y)=y となる。
もし P(x,y) が成り立たないなら、 P(x,t) を満たす y+1 未満の t は存在しないことになるので、 定義から h(x,y+1)=y+1 となる。
以上をまとめると、 h は、
h(x,0) = 0 h(x,y+1) = { h(x,y) (h(x,y)<y) y (h(x,y)=yANDP(x,y)) y+1 (h(x,y)=yANDNOTP(x,y))
という原始再帰の形で書ける。
この後者の式に現れる演算は、 命題 3.6, 命題 3.7, 定理 3.4, 定理 3.3, 命題 2.7 により全て原始再帰的である。
また、 場合分けも使われているが、 命題 4.1 によりこれは原始再帰性を保つ。
したがって、 P が原始再帰的であれば、 h も原始再帰的である。
この応用として、 除法が原始再帰的であることを示そう。
しかし、 原始再帰関数は全域でなければならない一方で、 0 での除算は普通定義されない。
そこで、 ここでは任意の x に対して x/0=x であることにしておく。
命題 4.4.
全域関数 div:2→ を
div(x,y):={ x (y=0) ⌊x/y⌋ (y>0)
で定めると、 これは原始再帰的である。
証明.
まず、 有界最小化を用いて、 f:2→ を、
f(x,y):=μt<x+1.x<t·y
と定める。
すると、 y>0 のときは、 x<t·y を満たす最小の t は ⌊x/y⌋+1 であるから、 この式の右辺は div(x,y)+1 に等しい。
一方 y=0 のときは、 x<t·y を満たす t は存在しないので、 この式の右辺は x+1 となり、 やはり div(x,y)+1 に等しい。
したがって、 この f を用いることで、 div は、
div(x,y)=f(x,y)∸1
と書ける。
ここまでに使用した演算は、 命題 2.7, 命題 2.8, 命題 3.6, 命題 2.11 および定理 4.3 により全て原始再帰的である。
したがって、 div も原始再帰的である。
以上、 我々は原始再帰的な関数や関係および原始再帰性を保つ操作を様々見てきた。
一度ここにまとめておこう。
- 定数 (定理 2.6)
- 加算, 減算, 乗算, 除算, 冪, 階乗 (命題 2.7, 命題 2.11, 命題 2.8, 命題 4.4, 命題 2.9, 命題 2.10)
- 総和, 総乗 (命題 2.14)
- 最大値, 最小値 (命題 2.13)
- 否定, 論理和, 論理積 (命題 3.3, 命題 3.4)
- 有界量化 (命題 3.5)
- 大小比較, 等号 (命題 3.6, 命題 3.7)
- 整除関係 (命題 3.8)
- 場合分け (命題 4.1)
- 有界最小化 (定理 4.3)
これらは全て原始再帰的 (もしくは原始再帰性を保つ) である。
したがって、 これらの合成や原始再帰で書けるものも全て原始再帰的になる。
このことから、 普段使うほとんどの関数や関係は原始再帰的であると言って良く、 逆に原始再帰的でない関数を作るのはなかなか難しい。
そのため、 「計算」 とは何なのかという疑問が生じ始めた当初は、 この 「計算できる」 関数とは原始再帰的関数であると考えられていた。
しかし、 Gabriel Sudan 等によって直感的に 「計算できる」 と思える関数で原始再帰的にならない例が発見され、 原始再帰関数の限界が明らかになった。
このような 「計算できそう」 だが原始再帰的にはならない関数のうち特に現在有名なのが、 Wilhelm Ackermann が考案した Ackermann 関数である。
これについては後で触れることにする。
次回はまだ、 原始再帰的関数について考えることにする。
次回は、 素数に関する演算が原始再帰的であることを見て、 自然数列のコーディングについて触れる。
参考文献
- H. B. Enderton (2011) 『Computability Theory』 Academic Press