日記 (2025 年 12 月 31 日)
第 6 回では、 「計算できそう」 だが原始再帰的ではない関数の例として Ackermann 関数を紹介した。
その後で、 「計算できそう」 な関数を含むクラスの候補として一般再帰関数を導入した。
そのため、 Ackermann 関数が一般再帰的でなかったら意味がないが、 幸いきちんと一般再帰的になっている。
今回は、 その証明を行う。
一般再帰的な範囲では最小化演算子が使えるので、 これをうまく使って Ackermann 関数を表現したい。
では、 どのように最小化演算子を使えば良いだろうか?
そのために、 まず Ackermann 関数の計算過程を観察してみよう。
例として ack(2,1) を考えることにする。
第 6 回にも記載したが、 これを計算する過程は次のようになる。
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
この途中には ack(-,-) の形が何重にもネストした形が現れるが、 よく見ると、 ack(-,-) のネストは常に右側でのみ起こることに気づくだろう。
すなわち、 ack(ack(-,-),-) のような形は決して表れない。
そのため、 ネストを平坦化してしまっても情報は失われない。
したがって、 出てくる数のみを並べて、
(2,1) → (1,2,0) → (1,1,1) → (1,0,1,0) → (1,0,0,1) → (1,0,2) → (1,3) → (0,1,2) → (0,0,1,1) → (0,0,0,1,0) → (0,0,0,0,1) → (0,0,0,2) → (0,0,3) → (0,4) → (5)
と書いても問題ない。
今後の便宜のため、 ここに出てくる (1,2,0) や (0,0,1,1) のような有限列に名前を付けておこう。
定義 8.1.
自然数の (長さ不定の) 有限数列を 「Ackermann 列 (— sequence)」 と呼ぶ。
さて、 上記のように Ackermann 関数の計算を Ackermann 列の変形と見なすのであれば、 この変形のルールは次のように書ける。
定義 8.2.
Ackermann 列の間の関係 → を、
(s,0,y) → (s,y+1) (s,x+1,0) → (s,x,1) (s,x+1,y+1) → (s,x,x+1,y)
として定める。
この右辺を左辺に変形することを 「Ackermann 変形 (— transformation)」 と呼ぶ。
すなわち Ackermann 変形とは、 与えられた Ackermann 列の最後の 2 つの数を見て、 それに応じてその 2 つの数を 1 つから 3 つの数に置き換える操作である。
ただし、 長さ 1 の Ackermann 列は変形することができないため、 そこまで来たら変形は終わりとする。
すると、 ある列 (x,y) から始めて Ackermann 変形を終わるまで繰り返せば、 最後に得られた Ackermann 列に属する唯一の数が ack(x,y) の値になる。
命題 8.3.
任意の数 x,y,z∈ に対し、 (x,y) で始まり (z) で終わる Ackermann 変形の列
(x,y)→s1→⋯→sn−1→(z)
が存在したとする。
このとき、 ack(x,y)=z が成り立つ。
証明.
Ackermann 関数と Ackermann 変形の定義からすぐに分かる。
以上の観察をすると、 Ackermann 関数の計算を最小化演算子で表現する方針が見えてくる。
まず、 関数 next を、 Ackermann 列を受け取ってそれを 1 段階変形した Ackermann 列を返す関数として作る。
なお、 受け取った Ackermann 列の長さが 1 だったら、 変形はすでに終了しているので、 それをそのまま返すことにする。
例えば、
next((2,1)) = (1,2,0) next((0,0,1,1)) = (0,0,0,1,0) next((5)) = (5)
である。
ここで、 ある列 (x,y) から n 回変形を繰り返して得られる Ackermann 列を seqat(x,y,n) と書くことにする。
この関数は、 上の next を使うことで、
seqat(x,y,0) = (x,y) seqat(x,y,n+1) = next(seqat(x,y,n))
という原始再帰の形で書ける。
これを用いると、 Ackermann 列の変形が n 回目で終わっているとは、 seqat(x,y,n)=seqat(x,y,n+1) が成り立つことだと言い換えられる。
つまり、 そのような n を最小化演算で取得すれば、 Ackermann 列の変形が終わるタイミングを取得できる。
すなわち、
n∞(x,y):=μn.seqat(x,y,n)=seqat(x,y,n+1)
とおくわけである。
すると、 変形が終わったタイミングでの Ackermann 列は seqat(x,y,n∞(x,y)) であり、 これは長さ 1 の列になっているはずなので、 この列に属する唯一の数としてめでたく ack(x,y) が得られる。
ということで、 後はこのアイデアを形式的に記述するだけである。
ただし、 Ackermann 列の取り扱いだけが少し問題になる。
我々が一般再帰関数として議論できるのは、 固定された個数の数を受け取って 1 つの数を返す関数のみである。
しかし、 Ackermann 列は長さ不定の有限数列であるから、 上で述べた next は長さ不定の有限数列を受け取って長さ不定の有限数列を返す関数になっている。
したがって、 このままではこれを一般再帰関数の理論に載せられない。
ただ、 我々は第 5 回で、 有限数列のコーディングについてすでに議論している。
このコーディングを用いれば、 有限数列を 1 つの数で表すことができるし、 そのように表された数からもとの有限数列を復元することも可能である。
そこで、 Ackermann 列をそのまま扱う代わりにそのコーディングを扱うことにして、 next 等を自然数上の関数として定義することを考える。
ただ、 有限列のコーディングを扱う上での準備が少し足りないので、 まずはその準備をしよう。
まず、 命題 5.5 で有限列 (のコーディング) から特定のインデックスの要素を抜き出す関数を用意したが、 このインデックスを右から数えるものを用意する。
命題 8.4.
全域関数 @:2→ であって、 任意の数 x0,⋯,xk−1,y∈ に対し、 y<k ならば、
⟨xk−1,⋯,x0⟩@y=xy
を満たし、 さらに原始再帰的なものが存在する。
証明.
@ を、
σ@y:=σ@(len(σ)∸y∸1)
と定めれば良い。
すなわち、 列のコーディング σ に対して、 σ@0 とはその列の最後の要素であり、 σ@1 とはその列の最後から 2 番目の要素である。
続いて、 列の最後の要素をいくつか取り除く関数も用意する。
命題 8.5.
全域関数 ↾:2→ であって、 任意の数 x0,⋯,xk−1,y∈ に対し、 y<k ならば、
⟨xk−1,⋯,x0⟩↾y=⟨xk−1,⋯,xy⟩
を満たし、 さらに原始再帰的なものが存在する。
証明.
↾ を、
σ↾y:=t<len(σ)∸ypr(t)(σ@t)+1
と定めれば良い。
最後に、 2 つの列を結合する関数を用意する。
命題 8.6.
全域関数 ∗:2→ であって、 任意の数 x0,⋯,xk−1,y0,⋯,yl−1∈ に対し、
⟨x0,⋯,xk−1⟩∗⟨y0,⋯,yl−1⟩=⟨x0,⋯,xk−1,y0,⋯,yl−1⟩
を満たし、 さらに原始再帰的なものが存在する。
証明.
∗ を、
σ∗τ:=σ·t<len(τ)pr(len(σ)+t)(σ@t)+1
と定めれば良い。
では、 本題に戻ろう。
まずは next を定義する。
これは、 Ackermann 列 (のコーディング) を受け取ってそれを 1 段階変形した Ackermann 列 (のコーディング) を返す関数である。
変形の規則は定義 8.2 の通りなので、 これを列のコーディングに基づいて書き直せば良い。
命題 8.7.
全域関数 next:→ であって、 次を満たすものが存在する。
- 任意の Ackermann 列 s に対して、 それが Ackermann 変形できるのならば、 変形後の列を s とすると next(⟨s⟩)=⟨s⟩ が成り立つ。
- 任意の Ackermann 列 s に対して、 それが Ackermann 変形できない (すなわち長さ 1) ならば、 next(⟨s⟩)=⟨s⟩ が成り立つ。
- next は原始再帰的である。
証明.
next を、
next(σ):={ σ (len(σ)≤1) (σ↾2)∗⟨(σ@0)+1⟩ (len(σ)>1,σ@1=0) (σ↾2)∗⟨(σ@1)∸1,1⟩ (len(σ)>1,σ@1>0,σ@0=0) (σ↾2)∗⟨(σ@1)∸1,σ@1,(σ@0)∸1⟩ (len(σ)>1,σ@1>0,σ@0>0)
と定めれば良い。
ここには原始再帰的な関数や操作しか使われていないので、 これは原始再帰的である。
すると、 すでに述べたアイデアにより、 Ackermann 関数が一般再帰的に表現できることが分かる。
定理 8.8.
Ackermann 関数は一般再帰的である。
証明.
まず、 関数 seqat:3→ を、
seqat(x,y,0) = ⟨x,y⟩ seqat(x,y,n+1) = next(seqat(x,y,n))
により定める。
命題 8.7 により next は原始再帰的だから、 この seqat も原始再帰的である。
これを用いて、 関数 n∞:2→ を、
n∞(x,y):=μn.seqat(x,y,n)=seqat(x,y,n+1)
により定めると、 これは一般再帰的である。
ここで、 任意の数 x,y に対して、
seqat(x,y,n∞(x,y))=next(seqat(x,y,n∞(x,y)))
が成り立つから、 命題 8.7 の next の性質により、 seqat(x,y,n∞(x,y)) は、 これ以上 Ackermann 変形できない長さ 1 の列のコーディングになっているはずである。
この列の唯一の要素を z:=seqat(x,y,n∞(x,y))@0 とおく。
すると、 各 i<n∞(x,y) について seqat(x,y,i) が表す数列を si と書けば、
(x,y)→s1→⋯→sn∞(x,y)−1→(z)
という Ackermann 変形の列が得られているので、 命題 8.3 により ack(x,y)=z が成り立つ。
すなわち、
ack(x,y)=seqat(x,y,n∞(x,y))@0
と書けるということである。
ここには一般再帰的な関数しか表れていないので、 これで ack が一般再帰的であることが示された。
このように、 式変形という操作を next という関数に落とし込むことで、 計算の終了タイミングを最小化により取得することができるので、 その最終結果も一般再帰的に取得できるというわけである。
この手法は、 Ackermann 関数に限らず、 式変形によって最終的に値を得られるように定義された関数であれば適用できる。
そのため、 直感的に 「計算できそう」 な関数は一般再帰的に書けると言えるだろう。
次回からは、 関数の理論から一旦離れて、 形式的な 「機械」 を扱っていくことにする。
参考文献
- CWoo (2013) 「Ackermann function is total recursive」 『PlanetMath』 https://planetmath.org/AckermannFunctionIsTotalRecursive
- CWoo (2013) 「Computing the Ackermann function」 『PlanetMath』 https://planetmath.org/ComputingTheAckermannFunction