アッカーマン関数を計算論の教科書の演習問題で見て、問題がうまく解けないのでためしにアッカーマン関数の計算結果の一部を一覧にして眺めようと思った。
でも、計算量が多すぎてすぐにとんでもないことになるんだね。お願いだから教科書に書いておいてくださいと思いました。
f 0 y = y + 1
f x 0 = f (x - 1) 1
f x y = f (x - 1) (f x (y - 1))
main = do print $ f 4 2
これをHaskellで実行すると死ぬ。
f 3 2 ぐらいはまだ大丈夫だが。
どのぐらい計算量がやばいことになるかを、f 2 2 の場合で置換モデルでノートに書き下していったら、なんと２７行もノートを使うということが判明。
f 4 2なんか、そりゃとんでもないことになってるんだろうなあ。
