日記 (2025 年 12 月 23 日)
今回からしばらくは、 再帰関数の理論を展開していくことになる。
Hilbert と Ackermann による疑問に対して、 Gödel が考案したのが一般再帰関数である。
Gödel による定義は方程式系を用いた少し複雑なものだったが、 後に Kleene によって整理された結果、 すでに知られていた原始再帰関数を拡張したものとして書けることが分かった。
そこで、 まずは原始再帰関数から導入していこう。
原始再帰関数とは、 ベースとなる関数から 「合成」 と 「原始再帰」 という 2 つの操作を繰り返して得ることのできる関数のことである。
合成とは、 知っての通りの関数合成のことだが、 改めて定式化しておこう。
定義 2.1.
部分関数 f0,⋯,fl−1:k→ および部分関数 g:l→ をとる。
部分関数 h:k→ が、 任意の x∈k に対して、
h(x)=g(f0(x),⋯,fl−1(x))
を満たすとき、 h は f0,⋯,fl−1,g から 「合成 (composition)」 で得られるという。
式を見れば分かるように、 上記の f0,⋯,fl−1,g に対して h は必ず一意に存在する。
なお、 前回述べた慣習通り、 上の等式は両辺が定義されて等しいか両辺とも定義されていないとき成立するので、 f0,⋯,fl−1,g のうち全域でないものがあると h が全域にならないことがある。
また、 上記の定義は l=0 の場合を含むことに注意せよ。
この場合は、 g:0→ とは定数のことだと見なせるから、 h はその g を値としてとる定数関数となる。
原始再帰は以下のように定義される。
定義 2.2.
部分関数 f:k→ および部分関数 g:k+2→ をとる。
部分関数 h:k+1→ が、 任意の x∈k,y∈ に対して、
h(x,0) = f(x) h(x,y+1) = g(x,y,h(x,y))
を満たすとき、 h は f,g から 「原始再帰 (primitive recursion)」 で得られるという。
これは、 我々がよく行う帰納的定義そのものである。
実際、 数学的帰納法等により、 上記の f,g に対して h が必ず一意に存在することが分かる。
ただし、 やはりこちらでも、 f,g のどちらか一方でも全域でなければ h も全域にはならない。
また、 上記の定義は k=0 の場合も含む。
この場合、 f:0→ は定数と見なせて、 上記 2 つの式は
h(0) = f h(y+1) = g(y,h(y))
と書き直せる。
原始再帰の能力は知るには実例を見るのが早いのだが、 後に原始再帰関数の具体例を挙げる際に何度も見ることになるので、 まずは原始関数の定義を行ってしまおう。
原始再帰関数とは、 ベースとなる関数から合成と原始再帰を繰り返して得られる関数のことなのだが、 そのベースとなる関数には次の 3 種類の関数を採用する。
定義 2.3.
全域関数 zero:0→, succ:1→, projnk:k→(0≤i<k) を
zero := 0 succ(x) := x+1 projik(x0,⋯,xk−1) := xi
で定め、 順に 「零関数 (zero function)」, 「後者関数 (successor function)」, 「射影関数 (projection function)」 と呼ぶ。
さらに、 これらを総称して 「初期関数 (initial function)」 と呼ぶ。
以上の準備のもと、 原始再帰関数は次のように定義できる。
定義 2.4.
部分関数が 「原始再帰的 (primitive recursive)」 であることを、 以下によって帰納的に定義する。
- 初期関数 zero, succ, projik(0≤i<k) は原始再帰的である。
- 部分関数 f0,⋯,fl−1:k→ および部分関数 g:l→ が全て原始再帰的ならば、 これらから合成で得られる部分関数 h:k→ も原始再帰的である。
- 部分関数 f:k→ および部分関数 g:k+2→ がともに原始再帰的ならば、 これらから原始再帰で得られる部分関数 h:k+1→ も原始再帰的である。
この定義からすぐに分かることとして、 原始再帰関数の全域性がある。
証明.
定義から、 初期関数は全て全域である。
また、 合成と原始再帰はどちらも全域関数から全域関数を作る。
したがって、 原始再帰関数は初期関数から合成と原始再帰を繰り返して得られるものであるから、 全て全域である。
では、 原始関数の具体例を見ていこう。
まず、 定数関数は全て原始再帰的であることが分かる。
証明.
まず、 一定して 0 を値にとる定数関数 z:k→ を考えると、 これは、
z(x)=zero
と書ける。
すなわち、 z は zero から合成で得られるため、 原始再帰的である。
次に、 一定して c∈ を値にとる定数関数 f:k→ を考える。
これは、 上の z を用いれば、
f(x)=succ(succ(⋯succ(⏟c 個z(x))⋯))
と書ける。
すなわち、 f は z に succ を c 回合成したものとして得られるため、 原始再帰的である。
続いて、 代表的な演算は全て原始再帰的であることを示そう。
まずは加法と乗法である。
命題 2.7.
加法関数 +:2→ は原始再帰的である。
証明.
まず、 全域関数 f:1→ および g:3→ を、
f(x) := proj01(x)=x g(x,y,z) := succ(proj23(x,y,z))=z+1
で定める。
すると、 f は proj01 そのものであるから原始再帰的で、 g も proj23 と succ の合成であるから原始再帰的である。
これらを用いることで、 加法関数 + は、
+(x,0) = f(x) +(x,y+1) = g(x,y,+(x,y))
と書ける。
すなわち、 + は f と g から原始再帰で得られるため、 原始再帰的である。
命題 2.8.
乗法関数 ×:2→ は原始再帰的である。
証明.
まず、 全域関数 f:1→ および g:3→ を、
f(x) := 0 g(x,y,z) := +(proj03(x,y,z),proj23(x,y,z))=x+z
で定める。
すると、 f は定数関数であるから定理 2.6 より原始再帰的で、 g も proj03, proj23, + の合成であるから命題 2.7 より原始再帰的である。
これらを用いることで、 乗法関数 × は、
×(x,0) = f(x) ×(x,y+1) = g(x,y,×(x,y))
と書ける。
すなわち、 × は f と g から原始再帰で得られるため、 原始再帰的である。
上の 2 つの証明の核心は、 + や × が原始再帰で得られるという点である。
上の証明でこれを示す際には、 原始再帰の定義に厳密に合わせるため、 かなり回りくどい記述をした。
例えば、 + の原始再帰性の証明には proj01 や proj23 を用いたが、 本質的には
+(x,0) = x +(x,y+1) = succ(+(x,y))
と書けると言っているにすぎない。
しかし、 原始再帰の定義に合わせるには、 +(x,0) の右辺は 1 変数関数の値でなければならないし、 +(x,y+1) の右辺には x や y が登場しなければならない。
この定義と辻褄を合わせるために、 何もしない関数として proj01 を挿入したり、 使わない変数を消すために proj23 を挿入したりしたのである。
× の原始再帰性の証明でも同様で、 その本質は、
×(x,0) = 0 ×(x,y+1) = +(x,×(x,y))
と表現できる点である。
しかし、 ×(x,0) の右辺で定数を関数値と見なすために f を導入したり、 ×(x,y+1) の右辺で y を消すために proj03 や proj23 を挿入したりすることになった。
このように、 初期関数に入れられている射影関数は、 式の中で用いる変数の数を調整したり入れ替えたりすることで定義と辻褄を合わせるために専ら使われる。
また、 定数関数も同様の用途で使われることが多い。
以降は、 このような本質的でない射影関数や定数関数を省略することにするので、 定義に厳密に則っているかどうかを確認する際は適宜補って読んでほしい。
では本題に戻り、 様々な演算が原始再帰的であることを示していこう。
加法と乗法を見たので、 次は冪と階乗を見る。
命題 2.9.
冪関数を pow:2→ と書くことにする。
すなわち、
pow(x,y):=xy
で定める。
これは原始再帰的である。
証明.
これは、
pow(x,0) = 1 pow(x,y+1) = x×pow(x,y)
と書け、 × から原始再帰で得られるため、 命題 2.8 より原始再帰的である。
命題 2.10.
階乗関数 !:1→ は原始再帰的である。
証明.
これは、
0! = 1 (x+1)! = x×x!
と書け、 × から原始再帰で得られるため、 命題 2.8 より原始再帰的である。
続いて、 減法を見ていこう。
しかし、 普通の減法の結果は負になる可能性があるため、 値域を自然数の範囲に収めるために、 負になったら 0 として扱うことにする。
命題 2.11.
全域関数 pred:1→ を
pred(x):={ x−1 (x>0) 0 (x=0)
で定めると、 これは原始再帰的である。
これは 「先行関数 (predecessor function)」 と呼ばれる。
証明.
これは、
pred(0) = 0 pred(x+1) = x
という原始再帰の形で書けるため、 原始再帰的である。
命題 2.12.
全域関数 ∸:2→ を
x∸y:={ x−y (x≥y) 0 (x<y)
で定めると、 これは原始再帰的である。
この演算はしばしば 「切り捨て減法 (truncated subtraction)」 や 「モナス (monus)」 と呼ばれる。
証明.
これは、
x∸0 = x x∸(y+1) = pred(x∸y)
と書け、 pred から原始再帰で得られるため、 命題 2.11 より原始再帰的である。
さらに、 最大値や最小値をとる関数も原始再帰的になる。
命題 2.13.
最小値関数 min:2→ および最大値関数 max:2→ はともに原始再帰的である。
証明.
実は最小値関数は、
min(x,y):=x∸(x∸y)
と書ける。
実際、 x≤y であれば x∸y=0 であるから x∸(x∸y)=x となり、 x>y であれば x∸y=x−y であるから x∸(x∸y)=y が成り立つ。
命題 2.12 より ∸ は原始再帰的であるため、 これを 2 回合成した min も原始再帰的である。
一方で最大値関数は、
max(x,y):=y+(x∸y)
と書ける。
実際、 x≤y であれば x∸y=0 であるから y+(x∸y)=y となり、 x>y であれば x∸y=x−y であるから y+(x∸y)=x が成り立つ。
命題 2.12 と命題 2.7 より ∸ と + は原始再帰的であるため、 これらを合成した max も原始再帰的である。
最後に、 総和と総乗を見て今回は終わりにしよう。
命題 2.14.
全域関数 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 も原始再帰的である。
証明.
Σf は、
Σf(x,0) = 0 Σf(x,y+1) = f(x,y)+Σf(x,y)
という原始再帰の形で書ける。
命題 2.7 より + が原始再帰的であるため、 f から原始再帰的なら Σf も原始再帰的である。
同様に Πf は、
Πf(x,0) = 0 Πf(x,y+1) = f(x,y)×Πf(x,y)
という原始再帰の形で書ける。
命題 2.8 より × が原始再帰的であるため、 f から原始再帰的なら Πf も原始再帰的である。
ということで、 原始再帰関数の例をいくつか見た。
次回は、 関数ではなく関係の原始再帰性を導入し、 その例を見ることにする。
参考文献
- H. B. Enderton (2011) 『Computability Theory』 Academic Press