アッカーマン関数

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動先: 案内検索

アッカーマン関数(アッカーマンかんすう、: Ackermann function)とは、非負整数 mn に対し、

によって定義される関数のことである。

与える数が大きくなると爆発的に計算量が大きくなるという特徴があり、性能測定などに用いられることもある。

また、数学的な意味として、原始再帰関数でないμ再帰関数の実例として有名である。これを(再帰のない手続き型の)プログラミング言語の言葉で言えば、whileループを使えばアッカーマン関数をプログラミングできるが、whileを使わずにforループだけでは実現不能だということである。

なお、アッカーマン関数のグラフは原始再帰的である。

アッカーマン関数の値の表[ソースを編集]

アッカーマン関数の計算は、無限の表を使った手順に言い換えることができる。まず、一番上の列に自然数を順番に並べる。表の値を決めるためは、すぐ左の値を見て、一つ上の列でその順番の値を取る。もし左に数値がない場合は、単に一つ上の列のカラム 1(n=1) の数値を取る。表の左上の部分は以下のようになる。

A(mn) の値
m\n 0 1 2 3 4 n
0 1 2 3 4 5
1 2 3 4 5 6
2 3 5 7 9 11
3 5 13 29 61 125
4 13 65533 265536 − 3 A(3, A(4, 3))=22265536-3
5 65533

A(4, A(5, 1)) A(4, A(5, 2)) A(4, A(5, 3))
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(mn) の値
m\n 0 1 2 3 4 n
0 0+1 1+1 2+1 3+1 4+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))
2 A(1,1) A(1,A(2,0)) A(1,A(2,1)) A(1,A(2,2)) A(1,A(2,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))
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))

6 A(5,1) A(5,A(6,0)) A(5,A(6,1)) A(5,A(6,2)) A(5,A(6,3))

参考文献[ソースを編集]

  • Y.Sundblad : The Ackermann Function. A theoretical, computational, and formulamanipulative study. BIT 11, 107-119 (1971)
  • 竹内外史『数学基礎論の世界 ロジックの雑記帳から』日本評論社、1972年、ISBN 4-535-78126-5
  • マイケル・シプサー著、『計算理論の基礎』太田和夫・田中圭介 監訳, 共立出版。原著: "Introduction to the Theory of Computation" (Michael Sipser, Thomson Course Technology)

関連項目[ソースを編集]

外部リンク[ソースを編集]