Ackermann関数 - Finite Groups Fun 有限群あるいはちょこっと計算ファンの日記

原始帰納的関数でない帰納的関数の例としてよく知られているAckermann関数 $\rm{Ack}(x,y)$ について，高橋正子著『計算論』近代科学社のP.22の練習問題を解いてみた．

ちょっと調べてみると1900年代の初期には計算可能な関数（今でいう帰納的関数）は全て原始帰納的関数であると信じられていたそうである．英語版Wikipediaによると，原始帰納的関数でない帰納的関数の具体的な例は，Ackermannのものが最初ではなく，1927年のGabriel SudanによるSudan関数が最初のものであったらしい（Ackermannのは1928年）.蛇足ながら，二人ともあのHirbertの弟子であったそうだ．Sudan関数も（オリジナルの）Ackermann関数も3変数の関数である．今，Ackermann関数と呼ばれる2変数の関数はRózsa PéterとRaphael Robinsonによるもの（1948年）で，Ackermann関数がSudan関数より有名なのは，恐らくこの2変数バージョンのおかげであろう．

ちなみにオリジナル3変数バージョンの定義は

$\rm{Ack}(0,0,y)=y$
$\rm{Ack}(0,x+1,y)=\rm{Ack}(0,x,y)+1$
$\rm{Ack}(1,0,y)=0$
$\rm{Ack}(z+2,0,y)=1$
$\rm{Ack}(z+1,x+1,y)=\rm{Ack}(z,\rm{Ack}(z+1,x,y),y)$

...らしい.

よく知られている2変数バージョンの定義はこうである．

$\rm{Ack}(0,y)=y+1$
$\rm{Ack}(x+1,0)=\rm{Ack}(x,1)$
$\rm{Ack}(x+1,y+1)=\rm{Ack}(x,\rm{Ack}(x+1,y))$

一見なんの変哲もない再帰的な定義である．しかし，問題を順に解いていくと，これがどんな原始帰納的関数よりも急速に増加することがわかってしまうという大変おいしい演習なのである．

(Q1) $\rm{Ack}(x,y)$ がうまく定義されている（ $N^2\to N$ なる関数である）ことを確かめよ．

(A1) $x$ を固定して考える． $x\ge N$ で， $\rm{Ack}(x,y)$ が既知の関数であるとする． $N=0$ の時は定義の一行目で成立している． $x=N+1$ のとき，2行目，3行目は既知の関数を使って $\rm{Ack}(x+1,y)$ の再帰的定義を与えているだけであるため， $\rm{Ack}(x+1,y)$ は定義されている．よって全ての $x$ について， $\rm{Ack}(x,y)$ は定義されている．□

(Q2) $\rm{Ack}(1,y)=y+2$ , $\rm{Ack}(2,y)=2y+3$ を示せ．また $\rm{Ack}(3,y)$ , $\rm{Ack}(4,y)$ を $y$ の関数として具体的に表せ．

(A1) すべて $y$ に関する帰納法で示せる．
$\rm{Ack}(1,0)=\rm{Ack}(0,1)=2$ と $\rm{Ack}(1,y+1)=\rm{Ack}(0,\rm{Ack}(1,y))=\rm{Ack}(1,y)+1$ より．

$\rm{Ack}(2,0)=\rm{Ack}(1,1)=3$ と $\rm{Ack}(2,y+1)=\rm{Ack}(1,\rm{Ack}(2,y))=\rm{Ack}(2,y)+2$ より．

$\rm{Ack}(3,y)=2^{y+3}-3$ .
$\rm{Ack}(4,y)={\overbrace{2^{2^{\dots^2}}}}^{y+3 \quad twos}-3$ .

(Q3) $x+y+1\le \rm{Ack}(x,y)$

(A3) $x$ に関する帰納法． $x=0$ の時, $\rm{Ack}(0,y)=y+1$ より成立している． $x\le N$ まで成立を仮定して， $y=0$ なら $\rm{Ack}(N+1,0)=\rm{Ack}(N,1)\ge N+1+1=(N+1)+0+1$ で成立. $y>0$ なら $\rm{Ack}(N+1,y)=\rm{Ack}(N,\rm{Ack}(x+1,y-1))\ge N+\rm{Ack}(N+1,y-1)+1$ となり，さらに $y$ に関する帰納法を適用すれば， $\rm{Ack}(N+1,y-1)\ge N+1+y-1+1=N+y+1$ を仮定するので， $\rm{Ack}(N+1,y)\ge 2N+y+2 \ge (N+1)+y+1$ であるから，二重の帰納法が完了する．□

(Q4) $\rm{Ack}(x,y)< \rm{Ack}(x,y+1)\le\rm{Ack}(x+1,y)$

(A4) $\rm{Ack}(x,y)< \rm{Ack}(x,y+1)$ を示す．
$x$ に関する帰納法． $x=0$ の時, $\rm{Ack}(0,y)=y+1<\rm{Ack}(x,y+1)=y+2$ より成立している． $x\le N$ まで成立を仮定して, $\rm{Ack}(N+1,y+1)=\rm{Ack}(N,\rm{Ack}(N+1,y))\ge (N+1)+\rm{Ack}(N+1,y)+1>\rm{Ack}(N+1,y)$ (∵ 最後にQ3を使った.) より， $x=N+1$ の時も成立する．
$\rm{Ack}(x,y+1)\le\rm{Ack}(x+1,y)$ を示す．
$y=0$ の時, $\rm{Ack}(x+1,0)=\rm{Ack}(x,1)$ より成立している． $y> 0$ の時，Q3の結果より $\rm{Ack}(x+1,y-1)\ge x+y+1 \ge y+1$ が成立するが，これと前半の結果（ $\rm{Ack}(x,y)$ が $y$ に関する単調増加関数であること）より， $\rm{Ack}(x,\rm{Ack}(x+1,y-1))>\rm{Ack}(x,y+1)$ が成立する．この式の左辺は， $\rm{Ack}(x+1,y)$ であるから証明は完了した．□

(Q5) 任意の $a,b\ge 0$ に対して $\rm{Ack}(a,\rm{Ack}(b,y))< \rm{Ack}(c,y)$ を満たす $c\ge 0$ が存在する．

(A5) $b-1\ge a$ ならば $\rm{Ack}(a,\rm{Ack}(b,y))<\rm{Ack}(b-1,\rm{Ack}(b,y))=\rm{Ack}(b,y+1)\le \rm{Ack}(b+1,y)$ (∵ Q4と定義を使った). よって $c=b+1$ とすればよい．
また $b-1 < a$ すなわち $a+1 > b$ のとき， $\rm{Ack}(b,y)<\rm{Ack(a+1,y)$ (∵ Q4）であるから，再びQ4より， $\rm{Ack}(a,\rm{Ack}(b,y))<\rm{Ack}(a,\rm{Ack(a+1,y))=\rm{Ack}(a+1,y+1)\ge \rm{Ack}(a+2,y)$ . よって $c=a+2$ とすればよい．いずれの場合でも $c=max(a+1,b)+1$ でよい. □

(Q6) 任意の原始帰納関数 $g:N^2\to N$ に対して, $c\ge 0$ が存在して，
$g(x_1,x_2,\dots,x_n)< \rm{Ack}(c,max(x_1,x_2,\dots,x_n))$ を満たす．

(A6) 原始帰納関数は，零関数 $\rm{zero}(x)=0$ ，後者関数 $\rm{suc}(x)=x+1$ ,射影関数 $p^n_i(x_1,x_2,\dots,x_n)=x_i$ か，それらの合成，原始帰納法の繰り返しによって生成された関数である．
結論を原始帰納関数の複雑さ（生成までに必要な合成および原始帰納法の適用の最小回数）に関する帰納法によって示す．
零関数，後者関数，射影関数に対しては，結論の成立は明らかである.

合成について， $f(\vec{x})=g(g_1(\vec{x}),g_2(\vec{x}),\dots,g_m(\vec{x}))$ とし， $g$ および $g_i$ に対して帰納法の仮定が満たされているとする．
$g(g_1(\vec{x}),g_2(\vec{x}),\dots,g_m(\vec{x}))<\rm{Ack}(c_g,max(g_1(\vec{x}),g_2(\vec{x}),\dots,g_m(\vec{x})))$
$\quad < \rm{Ack}(c_g,max(\rm{Ack}(c_{g_1},max(\vec{x})),\rm{Ack}(c_{g_2},max(\vec{x})),\dots,\rm{Ack}(c_{g_m},max(\vec{x})))$
$\quad <\rm{Ack}(c_g,\rm{Ack}(max(c_{g_i}),max(\vec{x})))<\rm{Ack}(c',max(\vec{x}))$ (∵ Q5を使った). よって，合成に関して結論は成立している．

原始帰納法についての結論の成立を示すために，次の2つの補題を先に証明する．

<補題1>
$\overbrace{\rm{Ack}(c,\rm{Ack}(c,\dots\rm{Ack}(c,y)))\dots)}^{n times} < \rm{Ack}(c+2,y+n)$

<証明>
$n$ に関する帰納法． $n=1$ の時は， $\rm{Ack}(c,y)<\rm{Ack}(c+2,y+1)$ は成立する． $n\le N$ まで成立すると仮定して，
$\overbrace{\rm{Ack}(c,\rm{Ack}(c,\dots\rm{Ack}(c,y)))\dots)}^{N+1 times} < \rm{Ack}(c,\rm{Ack}(c+2,y+n))<\rm{Ack}(c+1,\rm{Ack}(c+2,y+n))=\rm{Ack}(c+2,y+n+1)$ .
よって $n=N+1$ の時も成立する．□

<補題2>
$\rm{Ack}(c+1,2y) < \rm{Ack}(c+2,y)$

<証明>
$y$ に関する帰納法． $y=0$ の時は， $\rm{Ack}(c+1,0)<\rm{Ack}(c+2,0)$ で成立する． $y\le N$ まで成立すると仮定して， $\rm{Ack}(1,y)=y+2$ であったから，
$\rm{Ack}(c+1,2N+2)=\rm{Ack}(c+1,\rm{Ack}(1,2N))<\rm{Ack}(c+1,\rm{Ack}(c+1,2N))< \rm{Ack}(c+1,\rm{Ack}(c+2,N))=\rm{Ack}(c+2,N+1)$ .
よって $y=N+1$ の時も成立する．□

原始帰納法について，定義が次のように与えられているとして，
$\quad f(\vec{x},0)=g(\vec{x})$
$\quad f(\vec{x},y+1)=h(\vec{x},y,f(\vec{x},y))$
$g$ および $h$ について帰納法の仮定が満たされているとする．

$g(\vec{x})<\rm{Ack}(c_g,max(\vec{x}))$ また $h(\vec{x},y,z)<\rm{Ack}(c_h,max(\vec{x},y,z))$ として， $c=max(c_g,c_h)$ とする．
このとき，yに関する帰納法で
$f(\vec{x},y)<\overbrace{\rm{Ack}(c,\rm{Ack}(c,\dots\rm{Ack}(c,max(\vec{x},y))))\dots)}^{y+1 times}$
が示せる．さらに補題1より，
（右辺） $< \rm{Ack}(c+2,max(\vec{x},y)+y+1)<\rm{Ack}(c+3,max(\vec{x},y)+y)$ .
さらに $max(\vec{x},y)+y\le 2\times max(\vec{x},y)$ に注意すれば，補題2より，
$\rm{Ack}(c+3,max(\vec{x},y)+y)\le \rm{Ack}(c+3,2\times max(\vec{x},y))<\rm{Ack}(c+4,max(\vec{x},y))$ が得られ，原始帰納法についても，題意が成立していることが証明できた．□

以上の準備でAckermann関数が，原始帰納的関数でないことを証明することができる．

もし，Ackermann関数 $\rm{Ack}(x,y)$ が原始帰納的関数であったとすると,上のQ6の結果より， $\rm{Ack}(x,y)<\rm{Ack}(c,max(x,y))$ なる $c\ge 0$ が存在することになるが， $x=y=c$ としてみれば， $\rm{Ack}(c,c)<\rm{Ack}(c,c)$ と直ちに矛盾が導ける．よって，Ackermann関数は原始帰納的関数ではない．列挙して対角線要素を見るという対角線論法的な雰囲気が漂う面白い証明である.