アッカーマン関数

Ackermann function

巨大数を生み出す、計算可能な自然数上の全域関数

定義

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

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

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

Haskellで書くなら

code:hs

ack 0 n = n + 1

ack m 0 = ack (m-1) 1

ack m n = ack (m-1) $ ack m (n-1)

table:result

第1x∖第2y 0 1 2 3 4 5 ⋯

0 1 2 3 4 5 6 ⋯

1 2 3 4 5 6 7 ⋯

2 3 5 7 9 11 13 ⋯

3 5 13 29 61 125 253 ⋯

4 13 65533 2^65536−3 巨大巨大巨大 ⋯

5 65533 巨大巨大巨大巨大巨大 ⋯

... ... ... ... ... ... .. ...

https://gyazo.com/a1240985b1963893f5d0ffccf166b636

ハイパー演算子と以下の等式が成り立つ ref

ack m n=hyper(m,2,n+3) -3

計算機