1. 高校数学の美しい物語
  2. 巨大数:アッカーマン関数とは

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

更新日時 2021/03/07

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

目次
  • アッカーマン関数の定義

  • アッカーマン関数の計算

  • 性質

  • 応用

アッカーマン関数の定義

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

1: m=0m=0 のとき,A(0,n)=n+1A(0,n)=n+1

2: n=0n=0 のとき,A(m,0)=A(m1,1)A(m,0)=A(m-1,1)

3:それ以外のとき, A(m,n)=A(m1,A(m,n1))A(m,n)=A(m-1,A(m,n-1))

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

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

アッカーマン関数の計算

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

m\nm\backslash n 0 1 2 3 4 5 \cdots
0 11 22 33 44 55 66 \cdots
1 22 33 44 55 66 77 \cdots
2 33 55 77 99 1111 1313 \cdots
3 55 1313 2929 6161 125125 253253 \cdots
4 1313 6553365533 26553632^{65536}-3 巨大 巨大 巨大 \cdots
5 6553365533 巨大 巨大 巨大 巨大 巨大 \cdots
  • まず,一行目を定義式1によって埋めます(順番に正の整数を書いていくだけ)。
  • 次に,二行目の n=0n=0 の部分を定義式2によって埋めます(自分の右上の数字を書くだけ)。
  • さらに,二行目の n1n\geq 1 の部分を定義式3によって埋めます。3を使うときには「一つ上の行の A(m,n1)A(m,n-1) 番の数字」が A(m,n)A(m,n) になるので,自分の左隣の値と一つ上の行が埋まっていれば計算できます。
  • 同様に,三行目以降も計算していくことができます。

性質

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

性質1: m=0,1,2m=0,1,2 のとき,A(m,n)A(m,n)nn についての一次関数

性質2: m=3m=3 のとき,A(m,n)A(m,n)nn についての指数関数(をちょっと変形したもの)。

性質3:m4m\geq 4 のとき,A(m,n)A(m,n) は巨大な数字

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

A(0,n)=n+1,A(1,n)=n+2,A(2,n)=2n+3,A(3,n)=2n+33A(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))O(mf(n)) となることが知られています。

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

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

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

巨大な数を勝手に考えることはできますが,実際の問題に登場するというのが感動ポイントです。

  1. 高校数学の美しい物語
  2. 巨大数:アッカーマン関数とは