FANDOM


アッカーマン関数
基本関数 後者関数
急増加関数 \(f_{\omega}(n)\)

アッカーマン関数 \(A(x,y)\) は、ヴィルヘルム・アッカーマンが考案した帰納関数で、次の様に定義される[1][2]

非負整数 \(x,y\) に対して, \[ A(x,y)= \begin{cases} y+1 & \text{if}\ x=0, \\ A(x-1,1) & \text{if}\ x>0, y=0, \\ A(x-1,A(x,y-1)) & \text{otherwise}. \end{cases} \]

したがって、例えば次のように計算される。

\begin{align*} A(1,2) \ &=\ A(0,A(1,1))\\ \ &=\ A(0,A(0,A(1,0)))\\ \ &=\ A(0,A(0,A(0,1)))\\ \ &=\ A(0,A(0,2))\\ \ &=\ A(0,3)\\ \ &=\ 4, \\[3px] A(2,2)\ &=\ A(1,A(2,1))\\ \ &=\ A(1,A(1,A(2,0)))\\ \ &=\ A(1,A(1,A(1,1)))\\ \ &=\ A(1,A(1,A(0,A(1,0))))\\ \ &=\ A(1,A(1,A(0,A(0,1))))\\ \ &=\ A(1,A(1,A(0,2)))\\ \ &=\ A(1, A(1, 3))\\ \ &=\ A(1, A(0, A(1, 2)))\\ \ &=\ A(1, A(0, A(0, A(1, 1))))\\ \ &=\ A(1, A(0, A(0, A(0, A(1, 0)))))\\ \ &=\ A(1, A(0, A(0, A(0, A(0, 1)))))\\ \ &=\ A(1, A(0, A(0, A(0, 2))))\\ \ &=\ A(1, A(0, A(0, 3)))\\ \ &=\ A(1, A(0, 4))\\ \ &=\ A(1, 5)\\ \ &=\ A(0, A(1, 4))\\ \ &=\ A(0, A(0, A(1, 3)))\\ \ &=\ A(0, A(0, A(0, A(1, 2))))\\ \ &=\ A(0, A(0, A(0, A(0, A(1, 1)))))\\ \ &=\ A(0, A(0, A(0, A(0, A(0, A(1, 0))))))\\ \ &=\ A(0, A(0, A(0, A(0, A(0, A(0, 1))))))\\ \ &=\ A(0, A(0, A(0, A(0, A(0, 2)))))\\ \ &=\ A(0, A(0, A(0, A(0, 3))))\\ \ &=\ A(0, A(0, A(0, 4)))\\ \ &=\ A(0, A(0, 5))\\ \ &=\ A(0, 6)\\ \ &=\ 7. \end{align*}

\(x\)が小さいところでは、 \begin{align*} A(0,y) & = y+1, \\ A(1,y) & = y+2 &&= 2+(y+3)-3, \\ A(2,y) & = 2y+3 &&= 2\times(y+3)-3, \\ A(3,y) & = 2^{y+3}-3 &&= 2\uparrow (y+3)-3 \end{align*} などが確かめられる。一般には、矢印表記を用いて \[ A(x,y)=2\uparrow^{x-2}(y+3)-3 \qquad (x\ge3, y\ge0) \] と書くことができる。

アッカーマン関数は2重帰納関数(Double recursion)であり、いかなる原始再帰関数(原始帰納関数)[3]よりも増加速度が大きい[4]

アッカーマンのオリジナルの定義は、3変数であったとされる[5]が、現在はこの2変数の定義が有名となっている。

アッカーマン関数を多変数に拡張した多変数アッカーマン関数により、さらに増加率の高い関数を定義できる。

フリードマンの定義 編集

アッカーマン関数には、他にもいくつかの違った定義がある。Harvey Friedman は、アッカーマン関数を次のように定義した[6][7]

非負整数 \(x>0\), \(y\) に対して, \[ A(x,y)= \begin{cases} 1 & \text{if}\ y=0,\\ 2y & \text{if}\ x=1, y>0, \\ A(x-1,A(x,y-1)) & \text{otherwise}. \end{cases} \]

アッカーマン関数は、アッカーマン数と同じ程度の増加速度なので、関連づけられる。

アッカーマン関数は、しばしば一変数関数 \(A(n) = A(n, n)\) のことを意味する。

一変数アッカーマン関数 \(\alpha(n)\) の逆関数は、逆アッカーマン関数.[8]と言われる。アッカーマン関数は非常に増加率が高い関数であるため、逆アッカーマン関数は増加率が低い。時間複雑性理論に応用される。

Goucher の定義 編集

A.P. Goucher は、ブログの記事で以下のようなアッカーマン関数の定義を提案した[9]

\(f_1(n)=n+2\)

\(f_{m+1}(n) = f_m^n(2)\)

\(A(n) = f_n(n)\)

またこの投稿では次のような問題からアッカーマン関数の変種を考え出すことが出来る:

箱がいくつか並んでいて、コインが1枚づつ入っている。ここで、この箱に次のような操作を施す:

  • 一つの箱から1枚のコインを取り出し、その右の箱に2枚コインを入れる。
  • 一つの箱から1枚のコインを取り出し、その右の箱に入っているコインとそのさらに右の箱のコインの枚数を入れ替える。

右端の箱を除き箱にコインが入っていないという状況を考える。nを箱の個数とし、f(n)を右端のコインの個数の最大値とする。最初のほうの値は、 \[ \begin{array} \\ f(1) = 1 \\ f(2) = 3 \\ f(3) = 7 \\ f(4) = 28 \\ \end{array} \] である。[10]

ちなみに、2010年国際数学オリンピックの第五問は、f(6)>201020102010の証明だった。[11]

プログラム 編集

アッカーマン関数の計算を実行するプログラム[12][13][14]が書かれている。

出典 編集

  1. アッカーマン関数 (Wikipedia)
  2. Ackermann Function (Mathworld)
  3. 照井一成 (2005) 再帰的関数論
  4. [1]
  5. [2]
  6. THE ACKERMANN FUNCTION IN ELEMENTARY ALGEBRAIC GEOMETRY
  7. Ackermann function (Wikipedia)
  8. An inverse-Ackermann style lower bound for the online minimum spanning tree verification problem
  9. Goucher, Adam P. Fast-growing functions, part 1.
  10. [3]
  11. 数学オリンピックの問題
  12. 巨大数:アッカーマン関数のC++実装
  13. アッカーマン関数計算過程表示プログラム
  14. [4]

関連項目編集

広告ブロッカーが検出されました。


広告収入で運営されている無料サイトWikiaでは、このたび広告ブロッカーをご利用の方向けの変更が加わりました。

広告ブロッカーが改変されている場合、Wikiaにアクセスしていただくことができなくなっています。カスタム広告ブロッカーを解除してご利用ください。

FANDOMでも見てみる

おまかせWiki