アッカーマン関数
アッカーマン関数（アッカーマンかんすう）とは、非負整数 m と n に対し、
- <math>{\rm Ack}(m, n) = \begin{cases}
n + 1, & \mbox{ if }m = 0\\
{\rm Ack}(m - 1, 1), & \mbox{ if }n = 0\\
{\rm Ack}(m - 1, {\rm Ack}(m, n - 1)), & \mbox{ otherwise}\\
\end{cases}</math>
によって定義される関数のことである。
与える数が大きくなると爆発的に計算量が大きくなるという特徴があり、性能測定などに用いられることもある。また、数学的な意味として、原始再帰関数でないμ再帰関数の実例として有名である。
アッカーマン関数の値の表
アッカーマン関数の計算は、無限の表を使った手順に言い換えることができる。まず、一番上の列に自然数を順番に並べる。表の値を決めるためは、すぐ左の値を見て、一つ上の列でその順番の値を取る。もし左に数値がない場合は、単に一つ上の列のカラム 1 の数値を取る。表の左上の部分は以下のようになる。
| m\n | 0 | 1 | 2 | 3 | 4 | n |
|---|---|---|---|---|---|---|
| 0 | 1 | 2 | 3 | 4 | 5 | <math>n + 1</math> |
| 1 | 2 | 3 | 4 | 5 | 6 | <math>n + 2 = 2 + (n + 3) - 3</math> |
| 2 | 3 | 5 | 7 | 9 | 11 | <math>2n + 3 = 2 * (n + 3) - 3</math> |
| 3 | 5 | 13 | 29 | 61 | 125 | <math>2^{(n+3)} - 3</math> |
| 4 | 13 | 65533 | 265536 − 3 | <math>{2^{2^{65536}}} - 3</math> | A(3, A(4, 3)) | <math>\begin{matrix}\underbrace{{2^2}^{{\cdot}^{{\cdot}^{{\cdot}^2}}}} - 3 \\n\mbox{ + 3 twos}\end{matrix}</math> |
| 5 | 65533 |
<math>\begin{matrix}\underbrace{{2^2}^{{\cdot}^{{\cdot}^{{\cdot}^2}}}} - 3 \\65536\mbox{ twos}\end{matrix}</math> |
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 | <math>n + 1</math> |
| 1 | A(0,1) | A(0,A(1,0)) | A(0,A(1,1)) | A(0,A(1,2)) | A(0,A(1,3)) | <math>n + 2 = 2 + (n + 3) - 3</math> |
| 2 | A(1,1) | A(1,A(2,0)) | A(1,A(2,1)) | A(1,A(2,2)) | A(1,A(2,3)) | <math>2n + 3 = 2 * (n + 3) - 3</math> |
| 3 | A(2,1) | A(2,A(3,0)) | A(2,A(3,1)) | A(2,A(3,2)) | A(2,A(3,3)) | <math>2^{(n+3)} - 3</math> |
| 4 | A(3,1) | A(3,A(4,0)) | A(3,A(4,1)) | A(3,A(4,2)) | A(3,A(4,3)) |
<math>\begin{matrix}\underbrace{{2^2}^{{\cdot}^{{\cdot}^{{\cdot}^2}}}} - 3 \\n\mbox{ + 3 twos}\end{matrix}</math> |
| 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.テンプレート:Math-stub
