アッカーマン関数 - niming538の日記

アッカーマン関数(Ackermann's function)とは、非負整数 m と n に対し、
$Ack(m, n)=\{\begin{array}n+1,&if\quad m=0\\Ack(m-1,1),&if\quad n=0\\Ack(m-1,Ack(m,n-1)),& otherwise\\\end{array}$
によって定義される関数のことである。

 参考:  tex:Ack(m, n)=\{\begin{array}n+1,&if\quad m=0\\Ack(m-1,1),&if\quad n=0\\Ack(m-1,Ack(m,n-1)),&   otherwise\\\end{array}]

というのがあって、よくわからないなぁ、と思っていました。定義についてはWikipedia参照。

J言語のオンラインテキスト(Learning J)を読んでいたらセクション10.2の再帰(Recursion)のところにJ言語での定義が載っていましたので実験です。

   Ack =: 4 : 0
if.       x = 0  do.  y + 1                     
elseif.   y = 0  do.  (x - 1) Ack 1                 
elseif.   1      do.  (x - 1) Ack (x Ack y -1) 
end.
)

関数の定義は特に問題なく普通のようです。APL/J言語風に一行で書くのもあとで出てきますが、とりあえず今回の実験のためにはこれでOk。
あるレベルを超えると爆発的に再帰レベルが上がって計算量が増えますので、おそるおそるやってみます。

   0 Ack 0
1
   1 Ack 1 2
3
   1 Ack"0 0 (1 2)
3 4
   (i.4) Ack"0 0 table i.9
 +-------+--------------------------------+
 |Ack"0 0|0  1  2  3   4   5   6    7    8|
 +-------+--------------------------------+
 |0      |1  2  3  4   5   6   7    8    9|
 |1      |2  3  4  5   6   7   8    9   10|
 |2      |3  5  7  9  11  13  15   17   19|
 |3      |5 13 29 61 125 253 509 1021 2045|
 +-------+--------------------------------+

表にしたかったのでtableというツールをつかいましたが、これはなくてもいいし、/(スラッシュ)で工夫してもいいと思います。ランク"0 0は若干試行錯誤しました。

さて、この表の読み方ですが、左側の縦の一列が左側引数、上の横の一行が右側引数です。
(x - 1) Ack (x Ack y -1)
ですので、例えば2 Ack 2ならば1 Ack (2 Ack 1)になります。
ここで、2 Ack 1を見ると5なので2 Ack 2は1 Ack 5になります。
結果は7です。
同様に、2 Ack 3は1 Ack (2 Ack 2)で2 Ack 2は7なので、1 Ack 7で結果は9になります。
ここに表した数字より上は爆発的に桁数が増えて、計算ができなくなります。

Learning Jからの引き写しですが、非明示的(tacit)定義の方も載せておきます。

   c1 =: >:@]                NB. 1 + y
   c2 =: 

    
    <