巨大数：アッカーマン関数とは

とりあえず定義です。アッカーマン関数は以下の式によって再帰的に定義されます。

3つ目の式がポイントです。アッカーマン関数の引数にアッカーマン関数が入っています。

これだけではよく分からないと思うので，実際にアッカーマン関数を計算してみます。

アッカーマン関数の挙動を理解するには表を書くと分かりやすいです。

• まず，一行目を定義式1によって埋めます（順番に正の整数を書いていくだけ）。
• 次に，二行目の $n=0$ の部分を定義式2によって埋めます（自分の右上の数字を書くだけ）。
• さらに，二行目の $n\geq 1$ の部分を定義式3によって埋めます。3を使うときには「一つ上の行の $A(m,n-1)$ 番の数字」が $A(m,n)$ になるので，自分の左隣の値と一つ上の行が埋まっていれば計算できます。
• 同様に，三行目以降も計算していくことができます。

アッカーマン関数には以下の性質があります。

性質1と2に関しては，以下の式が数学的帰納法で簡単に証明できます：

$A(0,n)=n+1,\:A(1,n)=n+2,\\ A(2,n)=2n+3,\:A(3,n)=2^{n+3}-3$

性質3は定性的な表現ですので証明するようなことではありませんが，アッカーマン関数の最も重要な特徴です。

巨大な値を取るアッカーマン関数を定義して何が嬉しいのか？

アッカーマン関数は数学的に面白いというだけでなく，実際の問題に登場するのです！

私が知っている応用例としては「グラフ理論の問題の計算量の評価にアッカーマン関数の逆関数が登場する」というものです。

具体的には，例えば最小全域木問題の平均計算量が（かなり工夫したアルゴリズムを使うことで）$O(mf(n))$ となることが知られています。

ただし，$m$ はグラフの枝数，$n$ は頂点数，$f(n)$ はアッカーマン関数 $A(n,n)$ の逆関数です。

※プログラミングコンテストでのデータ構造を参考にしました。

アッカーマン関数は巨大な数なので，$n$ が非常に大きくなっても逆関数の値はなかなか大きくなりません。つまり，最小全域木問題はほとんど $O(m)$ の計算時間で解けるという素晴らしい結果です。