Ackermann関数（1）

最近、これを読んでいる。

計算論 計算可能性とラムダ計算 (コンピュータサイエンス大学講座)

この中でアッカーマン関数というのが出てくる。
原始的関数しか計算できないマシンでは計算できないが、帰納的関数が計算できるマシンでは計算できる関数の例としてよく知られているものらしい。

具体的には、次のよう（JavaScriptで書く）。

function ack(x, y) {

    if(x == 0)

        return y + 1;

    else if(y == 0)

        return ack(x - 1, 1);

    else

        return ack(x - 1, ack(x, y - 1));

}

ただし、x, yは非負整数。
こう書くと簡単そうに思えるが、ack(3,8)を計算しようとすると、「スタック領域が不足しています」というメッセージが出て落ちる。
ただし、この関数は高校2年程度(?)の数学の知識である程度明示的に表現できる。

ack(0, y) = y + 1
ack(1, y) = y + 2
ack(2, y) = 2y + 3
ack(3, y) = 2^y+3 - 3

ack(3, y)は、yがちょっと大きくなると非常に大きくなる。
しかし、次はもっと大きくなる。

ack(4, y) = 2^2…24 - 3

2の上に2がy個乗っていて、その上にさらに4が乗っている。
これをより具体的に書くと、

ack(4, 0) = 13
ack(4, 1) = 2¹⁶ - 3
ack(4, 2) = 2⁶⁵⁵³⁶ - 3

と、とてつもなく大きな数になる。
最後のは、10進で2万桁くらいかな。これだと計算できないわけではない。