日記 (2025 年 12 月 29 日)
前回までで、 原始再帰関数が非常に広い表現力をもっていることを見てきた。
そのため、 だいたいの 「計算できる」 と思える関数が原始再帰的な範囲内に収まっていそうに見えるが、 実は 「計算できそう」 でも原始再帰的でない関数の例がいくつか知られている。
今回は、 その例の 1 つである Ackermann 関数について触れようと思う。
Ackermann 関数とは、 以下の式で定義されるものである。
定義 6.1.
全域関数 ack:2→ を
ack(0,y) = y+1 ack(x+1,0) = ack(x,1) ack(x+1,y+1) = ack(x,ack(x+1,y))
で定める。
これを 「Ackermann 関数 (— function)」 と呼ぶ。
試しに定義に従って ack(2,1) を計算してみると、
ack(2,1) = ack(1,ack(2,0)) = ack(1,ack(1,1)) = ack(1,ack(0,ack(1,0))) = ack(1,ack(0,ack(0,1))) = ack(1,ack(0,2)) = ack(1,3) = ack(0,ack(1,2)) = ack(0,ack(0,ack(1,1))) = ack(0,ack(0,ack(0,ack(1,0)))) = ack(0,ack(0,ack(0,ack(0,1)))) = ack(0,ack(0,ack(0,2))) = ack(0,ack(0,3)) = ack(0,4) = 5
となる。
(2,1) という比較的小さい引数に対してもこのように膨大な回数の式変形が必要にはなるものの、 定義式に基づいて機械的に変形していけばどんな引数に対してもいずれは結果が求まる。
そのため、 この Ackermann 関数を 「計算できる」 と見なすのは直感的に納得できるだろう。
しかし、 Ackermann 関数は少なくとも原始再帰的ではない。
以降は、 これを示すことを目標とする。
まずは、 Ackermann 関数の左側の引数に小さい数を渡したときの具体的な値を観察してみよう。
命題 6.2.
任意の数 y∈ に対し、
ack(0,y) = y+1 ack(1,y) = 2+(y+3)−3=y+2 ack(2,y) = 2×(y+3)−3=2y+3
が成り立つ。
証明.
任意の y に対して ack(0,y)=y+1 が成り立つことは、 定義そのものである。
次に、 任意の y に対して ack(1,y)=y+2 が成り立つことを y に関する帰納法により示す。
基底ケースである y=0 のときは、 定義により、
ack(1,0)=ack(0,1)=1+1=2
が得られるので成り立つ。
次に帰納ステップのために、 ある y について ack(1,y)=y+2 が成り立つことを仮定すると、
ack(1,y+1)=ack(0,ack(1,y))=ack(0,y+2)=(y+2)+1=(y+1)+2
が得られる。
以上で、 2 つ目の式が示された。
最後に、 任意の y に対して ack(2,y)=2y+3 を、 y に関する帰納法により示す。
基底ケースである y=0 のときは、
ack(2,0)=ack(1,1)=1+2=3
となり成り立つ。
次に帰納ステップのために、 ある y について ack(2,y)=2y+3 が成り立つことを仮定すると、
ack(2,y+1)=ack(1,ack(2,y))=ack(1,2y+3)=(2y+3)+2=2(y+1)+3
が得られる。
以上で、 3 つ目の式も示された。
この右辺からはかなりの規則性が見出だせる。
+ を繰り返して得られる演算が × であることを踏まえると、 × を繰り返して得られる演算は冪であるから、 各 y∈ に対して、
ack(3,y)=2y+3−3
が成り立つと予想できる。
実際これは正しく、 上の命題と同様に帰納法で容易に示せる。
またさらに、 この次は冪を繰り返した演算になるはずなので、 各 y∈ に対して、
ack(4,y)=2⋰22⏟y+3 個−3
が成り立ちそうであり、 実際これも正しい。
このように、 Ackermann 関数の左側の引数は演算のネストのレベルのようなものを表していると解釈でき、 概ね ack(x,y) とは x 重にネストした演算を 2 に y 回適用させた数になると考えられる。
このことから、 Ackermann 関数の値は爆発的に増大していくことが分かる。
さて、 以降の議論で使うために、 Ackermann 関数に関する不等式をいくつか準備しておこう。
命題 6.3.
任意の数 x,y∈ に対し、
ack(x,y)>y
が成り立つ。
証明.
x に関する帰納法による。
基底ケースである x=0 のときは、 任意の y に対して、
ack(0,y)=y+1>y
であるから、 成立している。
帰納ステップのために、 ある x が存在して、 任意の y に対し ack(x,y)>y が成り立つことを仮定する。
この仮定を何度も使うと、 任意の y に対して、
ack(x+1,y) = ack(x,ack(x+1,y−1)) > ack(x+1,y−1) = ack(x,ack(x+1,y−2)) > ack(x+1,y−2) ⋮ > ack(x+1,0) = ack(x,1) > 1
という不等式の列が得られるが、 ここには y+1 個の不等式がある。
すなわち、
ack(x+1,y)>ack(x+1,y−1)>⋯>1⏟y+1 個
という形になっている。
これは自然の不等式だから不等号の左右には必ず 1 以上の差があるはずなので、 ack(x+1,y)>y+1 が成り立つ。
以上で帰納ステップも示され、 命題の主張が示された。
命題 6.4.
任意の数 x,y∈ に対し、
ack(x,y)<ack(x,y+1)
が成り立つ。
すなわち、 Ackermann 関数は右の変数に関して狭義単調増加である。
証明.
まず x=0 のときは、
ack(0,y)=y+1<y+2=ack(0,y+1)
であるから成り立っている。
x>0 のときは、 命題 6.3 を使うことで、
ack(x,y)<ack(x−1,ack(x,y))=ack(x,y+1)
と得られる。
命題 6.5.
任意の数 x,y∈ に対し、
ack(x,y+1)≤ack(x+1,y)
が成り立つ。
証明.
y に関する帰納法による。
基底ケースである y=0 のときは、 任意の x に対して、
ack(x,1)=ack(x+1,0)
であるから成り立っている。
帰納ステップのために、 ある y が存在して、 任意の x に対し ack(x,y+1)≤ack(x+1,y) が成り立つことを仮定する。
このとき、 任意の x に対して、 命題 6.3 により、
y+1<ack(x,y+1)
が得られる。
つまり、
y+2≤ack(x,y+1)
が成り立つということである。
これと命題 6.4 を使うことで、
ack(x,y+2)≤ack(x,ack(x,y+1))1
が分かる。
さらに命題 6.5 を使うことで、
ack(x,y+1)≤ack(x+1,y)
も得られるので、 再び命題 6.4 を使うことで、
ack(x,ack(x,y+1))≤ack(x,ack(x+1,y))2
が分かる。
式 1 と式 2 をまとめれば、
ack(x,y+2) ≤ ack(x,ack(x,y+1)) ≤ ack(x,ack(x+1,y)) = ack(x+1,y+1)
が得られ、 帰納ステップが示された。
以上で、 命題の主張も示された。
命題 6.6.
任意の数 x,y∈ に対し、
ack(x,y)<ack(x+1,y)
が成り立つ。
すなわち、 Ackermann 関数は左の変数に関して狭義単調増加である。
証明.
任意の x,y に対し、 命題 6.4 と命題 6.5 を使うことで、
ack(x,y)<ack(x,y+1)≤ack(x+1,y)
として得られる。
命題 6.7.
任意の数 x,y,z∈ に対し、
ack(x,ack(y,z))<ack(x+y+2,z)
が成り立つ。
証明.
任意の x,y,z に対し、 まず命題 6.6 により、
ack(y,z)<ack(x+y+1,z)
が得られる。
x≤x+y であることも踏まえれば、 これと命題 6.6 と命題 6.4 により、
ack(x,ack(y,z))<ack(x+y,ack(x+y+1,z))1
が分かる。
この右辺については、 命題 6.5 により、
ack(x+y,ack(x+y+1,z)) = ack(x+y+1,z+1)) ≤ ack(x+y+2,z))2
が得られる。
式 1 と式 2 を合わせれば、 命題の主張が得られる。
準備は以上にして、 Ackermann 関数が原始再帰的ではないことを示そう。
この際に重要になるのが、 次で定義する 「優越する」 という関係である。
定義 6.8.
全域関数 h:k→ および u:2→ をとる。
ある数 α∈ が存在して、 任意の x∈k に対して、
h(x)<u(α,max(x))
が成り立つとする。
このとき、 u は α で h を 「優越する (majorise)」 という。
Ackermann 関数はあらゆる原始再帰関数を優越することが知られている。
定義により、 Ackermann 関数がある関数 h を優越するとは、 Ackermann 関数の左の引数を適切に固定すれば、 常に h の値を Ackermann 関数の値で抑えられるということである。
ここで、 Ackermann 関数の左の引数は演算のネストのレベルのようなものだったことを思い出そう。
この見方をすれば、 この主張が述べているのは、 どんな原始再帰関数 h を用意しても、 演算のネストのレベルを十分大きくとれば、 その演算で h を上から抑えられてしまうということである。
逆の見方をすれば、 原始再帰関数の範囲では、 (加算から始めて) 有限回ネストして得られる演算よりも爆発的に増大するような関数は生み出せないということである。
では、 この事実を示そう。
定理 6.9.
全域関数 h:k→ を考える。
h が原始再帰的ならば、 Ackermann 関数は h を優越する。
証明.
h の構造に関する帰納法による。
まず、 h=zero であれば、
zero=0<1=ack(0,0)
であるから、 Ackermann 関数は 0 で zero を優越する。
h=succ であれば、 任意の x∈ に対して、 命題 6.2 により、
succ(x)=x+1<x+2=ack(1,x)
であるから、 Ackermann 関数は 1 で succ を優越する。
h=projik(i<k) であれば、 任意の x∈k に対して、
projik(x)=xi<max(x)+1=ack(0,max(x))
であるから、 Ackermann 関数は 0 で projik を優越する。
続いて h:k→ が合成で得られている場合を考える。
すなわち、 原始再帰関数 f0,⋯,fl−1:k→ および g:l→ によって、
h(x)=g(f0(x),⋯,fl−1(x))
と書ける。
帰納法の仮定として、 Ackermann 関数が f0,⋯,fl−1,g を全て優越するとする。
すなわち、 ある数 α0,⋯,αl−1,β が存在して、 任意の x∈k および y∈l に対して、
fi(x) < ack(αi,max(x)) g(y) < ack(β,max(y))(i<k)
が成り立つと仮定する。
ここで α:=max(α0,⋯,αl−1) とおくと、 任意の x∈k と任意の i<l に対して、 命題 6.4 により、
fi(x)<ack(αi,max(x))≤ack(α,max(x))
が成り立つが、 右辺は i に依存していないので、
max(f0(x),⋯,fl−1(x))<ack(α,max(x))
が分かる。
これを用いると、 適宜命題 6.4 や命題 6.7 を使うことで、
h(x) = g(f0(x),⋯,fl−1(x)) < ack(β,max(f0(x),⋯,fl−1(x))) < ack(β,ack(α,max(x))) < ack(β+α+2,max(x))
が得られる。
すなわち、 Ackermann 関数は β+α+2 で h を優越する。
最後に、 h:k+1→ が原始再帰で得られている場合を考える。
すなわち、 原始再帰関数 f:k→ および g:k+1→ によって、
h(x,0) = f(x) h(x,y+1) = g(x,y,h(x,y))
と書ける。
帰納法の仮定として、 Ackermann 関数が f,g をどちらも優越するとする。
すなわち、 ある数 α,β が存在して、 任意の x∈k と y,z∈ に対して、
f(x) < ack(α,max(x)) g(x,y,z) < ack(β,max(x,y,z))
が成り立つと仮定する。
今 γ:=max(α,β)+1 とおく。
ここで補題として、 任意の x∈k と y∈ に対して、
h(x,y)<ack(γ,max(x)+y))♡
が成り立つことを、 y に関する帰納法によって以下に示そう。
基底ケースの y=0 のときを考える。
任意の x に対して、 α<γ であることと命題 6.6 により、
h(x,0)=f(x)<ack(α,max(x))<ack(γ,max(x))
が成り立つので、 これで示された。
帰納ステップのため、 ある y が存在して、 y=y のときに任意の x に対して式 ♡ が成り立つことを仮定する。
するとまず、 任意の x に対して、 β≤γ−1 であることと命題 6.6 により、
h(x,y+1) = g(x,y,h(x,y)) < ack(β,max(x,y,h(x,y))) ≤ ack(γ−1,max(x,y,h(x,y)))♤1
が成り立つ。
ここで、 帰納法の仮定から
h(x,y)<ack(γ,max(x)+y)
が成り立ち、 さらに命題 6.3 により、
max(x,y)≤max(x)+y<ack(γ,max(x)+y)
も成り立つから、 両方を合わせれば、
max(x,y,h(x,y))<ack(γ,max(x)+y)
が得られる。
したがって命題 6.4 により、
ack(γ−1,max(x,y,h(x,y)) < ack(γ−1,ack(γ,max(x)+y)) = ack(γ,max(x)+y+1)♤2
が成り立つ。
したがって、 式 ♤1 と式 ♤2 を合わせれば、
h(x,y+1)<ack(γ,max(x)+y+1)
が得られるので、 これで帰納ステップが示された。
以上により、 任意の x∈k と y∈ に対して、 式 ♡ すなわち
h(x,y)<ack(γ,max(x)+y))
が成り立つことが分かった。
ここで、 命題 6.2 により、
max(x)+y < 2max(x,y) ≤ 2max(x,y)+3 = ack(2,max(x,y))
であるから、 これと式 ♡ を命題 6.4 で合わせて、 最後に命題 6.7 を使うことで、
h(x,y) < ack(γ,max(x)+y)) < ack(γ,ack(2,max(x,y))) < ack(γ+4,max(x,y)))
が得られる。
すなわち、 Ackermann 関数は γ+4 で h を優越する。
以上で全体の帰納法が回ったので、 命題の主張の証明が完了した。
さて、 これで Ackermann 関数があらゆる原始再帰関数を優越することが分かった。
一方、 実は自分自身を優越することはできないため、 Ackermann 関数は原始再帰的にはなり得ないことがこれで分かる。
命題 6.10.
全域関数 u:2→ に対し、 u が u 自身を優越することはない。
証明.
仮に u が u 自身を優越すると仮定する。
すると、 ある数 α が存在して、 任意の x,y に対して、
u(x,y)<u(α,max(x,y))
が成り立つことになるが、 特に
u(α,α)<u(α,max(α,α))=u(α,α)
が得られてしまい、 矛盾が生じる。
したがって、 u が u 自身を優越することはない。
定理 6.11.
Ackermann 関数は原始再帰的ではない。
証明.
仮に Ackermann 関数が原始再帰的であったとすると、 定理 6.9 により Ackermann 関数が Ackermann 関数自身を優越することになるが、 それは命題 6.10 に矛盾する。
したがって、 Ackermann 関数は原始再帰的ではない。
ということで、 Ackermann 関数を 「計算できる」 関数から除外するのは直感的ではない一方、 Ackermann 関数は原始再帰的でないことが分かってしまったので、 「計算できる」 関数の定義として原始再帰関数を採用するのは不適切であると言える。
そのため、 原始再帰関数よりも広い関数のクラスを模索する必要がある。
それが一般再帰関数である。
次回からは、 一般再帰関数の理論を進めていく。
参考文献
- CWoo (2013) 「Ackermann function is not primitive recursive」 『PlanetMath』 https://planetmath.org/AckermannFunctionIsNotPrimitiveRecursive