アッカーマン関数
出典: フリー百科事典『ウィキペディア（Wikipedia）』
アッカーマン関数（アッカーマンかんすう）とは、非負整数 m と n に対し、
によって定義される関数のことである。
与える数が大きくなると爆発的に計算量が大きくなるという特徴があり、性能測定などに用いられることもある。また、数学的な意味として、原始帰納的関数でない帰納的関数の実例として有名である。
目次 |
[編集] アッカーマン関数の値の表
アッカーマン関数の計算は、無限の表を使った手順に言い換えることができる。まず、一番上の列に自然数を順番に並べる。表の値を決めるためは、すぐ左の値を見て、一つ上の列でその順番の値を取る。もし左に数値がない場合は、単に一つ上の列のカラム 1 の数値を取る。表の左上の部分は以下のようになります。
| m\n | 0 | 1 | 2 | 3 | 4 | n |
|---|---|---|---|---|---|---|
| 0 | 1 | 2 | 3 | 4 | 5 | n + 1 |
| 1 | 2 | 3 | 4 | 5 | 6 | n + 2 = 2 + (n + 3) − 3 |
| 2 | 3 | 5 | 7 | 9 | 11 | 2n + 3 = 2 * (n + 3) − 3 |
| 3 | 5 | 13 | 29 | 61 | 125 | 2(n + 3) − 3 |
| 4 | 13 | 65533 | 265536 − 3 |  |
A(3, A(4, 3)) |  |
| 5 | 65533 |
|
A(4, A(5, 1)) | A(4, A(5, 2)) | A(4, A(5, 3)) | A(4, A(5, n-1)) |
| 6 | A(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)) |
再帰的な参照で表示している値は非常に大きく、他の形式では簡単に表現することはできない。
表のごく最初の部分の値にも関わらず、グラハム数や短いクヌースの矢印表記で表現することのできない、非常に大きな値が定義されている。この値は、アッカーマン関数をそれ自身に再帰的に適用する方法で作られている。
以下は、上記のテーブルと同じものであるが、パターンを分かりやすくするため、値を関数定義の表現に置き換えている。
| m\n | 0 | 1 | 2 | 3 | 4 | n |
|---|---|---|---|---|---|---|
| 0 | 0+1 | 1+1 | 2+1 | 3+1 | 4+1 | n + 1 |
| 1 | A(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 |
| 2 | A(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 |
| 3 | A(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 |
| 4 | A(3,1) | A(3,A(4,0)) | A(3,A(4,1)) | A(3,A(4,2)) | A(3,A(4,3)) |
|
| 5 | A(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)) |
| 6 | A(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.
 |
この項目「アッカーマン関数」は、数学に関連した書きかけの項目です。加筆・訂正などをして下さる協力者を求めています。（ポータル 数学／ウィキプロジェクト 数学） |
