2015/02/13

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

分野: いろんな関数  レベル: マニアック

アッカーマン関数 $A(m,n)$ とは,非負整数 $m,n$ を入力とする二変数関数であり,$m\geq 4$ のときに猛烈に大きい値を取る。

アッカーマン関数の定義

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

1:$m=0$ のとき,$A(0,n)=n+1$
2:$n=0$ のとき,$A(m,0)=A(m-1,1)$
3:それ以外のとき, $A(m,n)=A(m-1,A(m,n-1))$

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

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

アッカーマン関数の計算

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

$m\backslash n$ 0 1 2 3 4 5 $\cdots$
0 1 2 3 4 5 6 $\cdots$
1 2 3 4 5 6 7 $\cdots$
2 3 5 7 9 11 13 $\cdots$
3 5 13 29 61 125 253 $\cdots$
4 13 65533 $2^{65536}-3$ 巨大 巨大 巨大 $\cdots$
5 65533 巨大 巨大 巨大 巨大 巨大 $\cdots$
  • まず,一行目を定義式1によって埋めます(順番に正の整数を書いていくだけ)。
  • 次に,二行目の $n=0$ の部分を定義式2によって埋めます(自分の右上の数字を書くだけ)。
  • さらに,二行目の $n\geq 1$ の部分を定義式3によって埋めます。3を使うときには「一つ上の行の $A(m,n-1)$ 番の数字」が $A(m,n)$ になるので,自分の左隣の値と一つ上の行が埋まっていれば計算できます。
  • 同様に,三行目以降も計算していくことができます。

性質

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

性質1:$m=0,1,2$ のとき,$A(m,n)$ は $n$ についての一次関数
性質2:$m=3$ のとき,$A(m,n)$ は $n$ についての指数関数(をちょっと変形したもの)。
性質3:$m\geq 4$ のとき,$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)$ の計算時間で解けるという素晴らしい結果です。

巨大な数を勝手に考えることはできますが,実際の問題に登場するというのが感動ポイントです。
分野: いろんな関数  レベル: マニアック