アッカーマン関数（アッカーマンかんすう）とは、非負整数 m と n に対し、
によって定義される関数のことである。
与える数が大きくなると爆発的に計算量が大きくなるという特徴があり、性能測定などに用いられることもある。また、数学的な意味として、原始帰納的関数でない帰納的関数の実例として有名である。
目次
1 アッカーマン関数の値の表
2 参考文献
3 関連項目
4 外部リンク
//
アッカーマン関数の計算は、無限の表を使った手順に言い換えることができる。まず、一番上の列に自然数を順番に並べる。表の値を決めるためは、すぐ左の値を見て、一つ上の列でその順番の値を取る。もし左に数値がない場合は、単に一つ上の列のカラム 1 の数値を取る。表の左上の部分は以下のようになる。
A(m, n) の値m\n01234n
012345n + 1
123456n + 2 = 2 + (n + 3) ? 3
23579112n + 3 = 2 * (n + 3) ? 3
351329611252(n + 3) ? 3
41365533265536 ? 3A(3, A(4, 3))
565533
A(4, A(5, 1))A(4, A(5, 2))A(4, A(5, 3))A(4, A(5, n-1))
6A(5, 1)A(5, A(6, 0))A(5, A(6, 1))A(5, A(6, 2))A(5, A(6, 3))A(5, A(6, n-1))
再帰的な参照で表示している値は非常に大きく、他の形式では簡単に表現することはできない。
このように表のごく最初の部分でも既に巨大な値が現れているが、さらに、グラハム数のような、短いクヌースの矢印表記では表現することのできない非常に大きな値も定義される。この数は、アッカーマン関数をそれ自身に再帰的に適用するのに類似した方法で作られている。
以下は、上記のテーブルと同じものであるが、パターンを分かりやすくするため、値を関数定義の表現に置き換えている。
A(m, n) の値m\n01234n
00+11+12+13+14+1n + 1
1A(0,1)A(0,A(1,0))A(0,A(1,1))A(0,A(1,2))A(0,A(1,3))n + 2 = 2 + (n + 3) ? 3
2A(1,1)A(1,A(2,0))A(1,A(2,1))A(1,A(2,2))A(1,A(2,3))2n + 3 = 2 * (n + 3) ? 3
3A(2,1)A(2,A(3,0))A(2,A(3,1))A(2,A(3,2))A(2,A(3,3))2(n + 3) ? 3
4A(3,1)A(3,A(4,0))A(3,A(4,1))A(3,A(4,2))A(3,A(4,3))
5A(4,1)A(4,A(5,0))A(4,A(5,1))A(4,A(5,2))A(4,A(5,3))
A(4, A(5, n-1))
6A(5,1)A(5,A(6,0))A(5,A(6,1))A(5,A(6,2))A(5,A(6,3))
A(5, A(6, n-1))
参考文献
Y.Sundblad : The Ackermann Function. A theoretical, computational, and formulamanipulative study. BIT 11, 107-119 (1971)
竹内外史『数学基礎論の世界 ロジックの雑記帳から』日本評論社、1972年、ISBN 4-535-78126-5
関連項目
巨大数
ヴィルヘルム・アッカーマン
外部リンク
Weisstein, Eric W. " ⇒Ackermann Function." From MathWorld.
などをして下さる協力者を求めています。（P:数学／PJ:数学）
カテゴリ: 組合せ論 | 特殊関数 | 数学に関する記事 | 数学関連のスタブ項目
更新日時:2008年8月13日(水)03:03
取得日時:2008/11/18 17:10
