巨大数資料wiki
巨大数資料wiki

アッカーマン関数

アッカーマン関数とは、自然数m,nを変数とした関数で、Ack(m,n)またはAk(m,n)またはA(m,n)などと表記される。

定義

1. A(0,n)=n+1
2. A(m,0)=A(m-1,1)
3. A(m,n)=A(m-1,A(m,n-1))

とりあえず、定義にしたがって、例えばA(10,10)を展開しようとすると、

A(10,10)
=A(9,A(10,9))
=A(9,A(9,A(10,8))))
=A(9,A(9,A(9,A(10,7)))))
=・・・

　訳がわからないことになります。
　ただ、変形する毎に、括弧の階層が重なる、ということは、チェーン表記でもやったように、階層を縦に記述する記法を用いれば、もうちょっと解りやすくなるのではないか、という事になります。

A(10,10)= \begin{matrix}{ A(9,\underset{\Uparrow}{\quad}) \\ \overline{A(10,9)} }\end{matrix}= \begin{matrix}{ A(9,\underset{\Uparrow}{\quad}) \\ \overline{A(9,\underset{\Uparrow}{\quad})} \\ \overline{A(10,8)} }\end{matrix}= \begin{matrix}{ A(9,\underset{\Uparrow}{\quad}) \\ \overline{A(9,\underset{\Uparrow}{\quad})} \\ \overline{A(9,\underset{\Uparrow}{\quad})} \\ \overline{A(10,7)} }\end{matrix}=\dots

　この変形の仕方、実はチェーン表記と良く似ています。チェーン表記では、…→y→zのzを減らしてyを変形する、というのが基本手法でした。結果、数のオーダーを決める重要度はzが最重要で、yはその次に重要、となりました。
　一方このアッカーマンではどうでしょうか、A(m,n)のmを減らしてnを変形させる、ということは、数のオーダーを決める最重要項目は、nよりもmということにならないでしょうか。
　チェーン表記においては、…→y→2、…→y→3、…→y→4と帰納的に実体を見ていきました。アッカーマンにおいても同様に、A(0,n)は定義より明らかにn+1ですから置いといて、A(1,n)、A(2,n)、A(3,n)、…について順々に実体を見ていけば、アッカーマン全体の実体が見えてきそうです。

A(1,n)

\newcommand{\katamari}{ \left\begin{matrix}{ A(0,\underset{\Uparrow}{\quad}) \\ \overline{A(0,\underset{\Uparrow}{\quad})} \\ \vdots \\ \overline{A(0,\underset{\Uparrow}{\quad})} \\ \overline{A(0,\underset{\Uparrow}{\quad})} }\end{matrix}\right\}n } </p><p>A(1,n)= \begin{matrix}{ A(0,\underset{\Uparrow}{\quad}) \\ \overline{A(1,n-1)} }\end{matrix}=\dots=\left\begin{matrix}{ A(0,\underset{\Uparrow}{\quad}) \\ \overline{A(0,\underset{\Uparrow}{\quad})} \\ \vdots \\ \overline{A(0,\underset{\Uparrow}{\quad})} \\ \overline{A(1,1)} }\end{matrix}\right\}n = \begin{matrix}{\katamari \\ \overline{A(1,0)}\qquad}\end{matrix}

\newcommand{\katamari}{ \left\begin{matrix}{ A(0,\underset{\Uparrow}{\quad}) \\ \overline{A(0,\underset{\Uparrow}{\quad})} \\ \vdots \\ \overline{A(0,\underset{\Uparrow}{\quad})} }\end{matrix}\right\}n } </p><p>=\begin{matrix}{\katamari \\ \overline{A(0,1)}\qquad}\end{matrix} =\begin{matrix}{\katamari \\ \overline{2}}\end{matrix}

A(0,k)=k+1なので、

=((\dots((2)\underbrace{+1)+1\dots)+1)+1}_{n}=2+nとなる。

\newcommand{\unitI}{\underset{\Uparrow}{\quad}} \newcommand{\unitII}{\overline{A(1,\unitI)}} \newcommand{\unitIII}{\left\begin{matrix} </p> <pre>A(1,\unitI) \\ \unitII \\ \vdots \\ \unitII \\ \unitII \\ </pre> <p>\end{matrix}\right\}n } </p><p>A(2,n)= \begin{matrix} </p> <pre>A(1,\unitI) \\ \overline{A(2,n-1)} </pre> <p>\end{matrix}=\dots=\left\begin{matrix} </p> <pre>A(1,\unitI) \\ \unitII \\ \vdots \\ \unitII \\ \overline{A(2,1)} \\ </pre> <p>\end{matrix}\right\}n=\left\begin{matrix} </p> <pre>\unitIII \\ \overline{A(2,0)}\qquad </pre> <p>\end{matrix}

タグ：

増加関数 アッカーマン関数 巨大数
+ タグ編集
  • タグ：
  • 増加関数
  • アッカーマン関数
  • 巨大数
タグの更新に失敗しました
エラーが発生しました。ページを更新してください。
ページを更新
「アッカーマン関数」をウィキ内検索
最終更新：2024年07月26日 20:05