アッカーマン関数
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で書くなら
hsack 0 n = n + 1
ack m 0 = ack (m-1) 1
ack m n = ack (m-1) $ ack m (n-1)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 | 巨大 | 巨大 | 巨大 | 巨大 | 巨大 | ⋯ |
| ... | ... | ... | ... | ... | ... | .. | ... |
ack m n = hyper(m,2,n+3) -3 計算機
関連
アッカーマン関数を60~70回繰り返すものと同じ
めちゃくちゃでかい
参考