アッカーマン関数

アッカーマン関数とは、自然数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}

タグ:

+ タグ編集
  • タグ:

このサイトはreCAPTCHAによって保護されており、Googleの プライバシーポリシー利用規約 が適用されます。

最終更新:2013年12月17日 21:09