アッカーマン関数の定義と解
アッカーマン関数の定義
\(m,n\in\mathbb{Z}_{0}\)とする。
\[ A\left(m,n\right)=\begin{cases} n+1 & m=0\\ A\left(m-1,1\right) & n=0\\ A\left(m-1,A\left(m,n-1\right)\right) & otherwise \end{cases} \]
\(m,n\in\mathbb{Z}_{0}\)とする。
\[ A\left(m,n\right)=\begin{cases} n+1 & m=0\\ A\left(m-1,1\right) & n=0\\ A\left(m-1,A\left(m,n-1\right)\right) & otherwise \end{cases} \]
アッカーマン関数の解
\(m,n\in\mathbb{Z}_{0}\)とする。
\[ A\left(m,n\right)=2\uparrow^{m-2}\left(n+3\right)-3 \]
\(m,n\in\mathbb{Z}_{0}\)とする。
\[ A\left(m,n\right)=2\uparrow^{m-2}\left(n+3\right)-3 \]
-
\(a\uparrow^{n}b\)はクヌースの矢印表記\(m=0\)のとき
\(n=0\)のとき定義より\(A\left(0,0\right)=1\)、与式より\(A\left(0,0\right)=\left(2\uparrow^{-2}3\right)-3=4-3=1\)となるので成り立つ。\(n=k\)のとき成り立つと仮定すると、
\begin{align*} A\left(0,k+1\right) & =k+1+1\\ & =A\left(0,k\right)+1\\ & =2\uparrow^{-2}\left(k+3\right)-3+1\\ & =2\uparrow^{-2}\left(k+4\right)-3\\ & =2\uparrow^{-2}\left(\left(k+1\right)+3\right)-3 \end{align*} となるので、\(n=k+1\)でも成り立つ。
故に数学的帰納法より、
\[ A\left(0,n\right)=2\uparrow^{-2}\left(n+3\right)-3 \] は成り立つ。
\(m=1\)のとき
\(n=0\)のとき定義より\(A\left(1,0\right)=A\left(0,1\right)=2\)、与式より\(A\left(1,0\right)=2\uparrow^{-1}3-3=5-3=2\)となるので成り立つ。\(n=k\)のとき成り立つと仮定すると、
\begin{align*} A\left(1,k+1\right) & =A\left(0,A\left(1,k\right)\right)\\ & =A\left(1,k\right)+1\\ & =2\uparrow^{-1}\left(k+3\right)-3+1\\ & =2+k+4-3\\ & =2\uparrow^{-1}\left(\left(k+1\right)+3\right)-3 \end{align*} となるので、\(n=k+1\)でも成り立つ。
故に数学的帰納法より、
\[ A\left(1,n\right)=2\uparrow^{-1}\left(n+3\right)-3 \] は成り立つ。
\(n=0\)のとき、
\(m=0\)のとき、定義より\(A\left(0,0\right)=1\)、与式より、\(A\left(0,0\right)=\left(2\uparrow^{-2}3\right)-3=4-3=1\)となるので成り立つ。\(m=k\)のとき、成り立つと仮定すると、
\begin{align*} A\left(k+1,0\right) & =A\left(k,1\right)\\ & =2\uparrow^{k-2}4-3\\ & =2\uparrow^{k-2}\left(2\uparrow^{k-1}2\right)-3\\ & =2\uparrow^{k-1}3-3\\ & =2\uparrow^{\left(k+1\right)-2}3-3 \end{align*} となるので、\(m=k+1\)でも成り立つ。
故に数学的帰納法より、
\[ A\left(m,0\right)=2\uparrow^{m-2}3-3 \] は成り立つ。
-
これより、\(A\left(0,n\right)\)と\(A\left(1,n\right)\)と\(A\left(m,0\right)\)で成り立つ。\(m=u\)かつ\(n=v\)で\(A\left(u,v\right)\)が成り立ち、\(u=m-1\)かつ任意の\(v\)のとき\(A\left(u,v\right)\)でも成り立つと仮定すると、
\begin{align*} A\left(u,v+1\right) & =A\left(u-1,A\left(u,v\right)\right)\\ & =2\uparrow^{u-3}\left(A\left(u,v\right)+3\right)-3\\ & =2\uparrow^{u-3}\left(2\uparrow^{u-2}\left(v+3\right)\right)-3\\ & =2\uparrow^{u-2}\left(v+4\right)-3\\ & =2\uparrow^{u-2}\left(\left(v+1\right)+3\right)-3 \end{align*} となるので\(n=v+1\)でも成り立つ。
これより、\(A\left(2,0\right)\)で成り立つので、\(\forall n\in\mathbb{N}_{0},A\left(2,n\right)\)で成り立ち、同様に\(\forall n\in\mathbb{N}_{0},A\left(3,n\right)\)で成り立ち、\(\forall m,n\in\mathbb{N}_{0},A\left(m,n\right)\)で成り立つ。
故に題意は成り立つ。
ページ情報
| タイトル | アッカーマン関数の定義と解 |
| URL | https://www.nomuramath.com/lv1zgcex/ |
| SNSボタン |
反復コンウェイのチェーン表記
\[
X\rightarrow\left(p+1\right)\rightarrow\left(q+1\right)=f^{p\circ}\left(X\right)
\]
2年生の夢(高さ2のテトレーションの0から1までの定積分)
\[
\int_{0}^{1}\frac{1}{x^{x}}dx=\sum_{k=1}^{\infty}\frac{1}{k^{k}}
\]
ハイバー演算子の基本的な値
\[
H_{n}\left(0,a\right)=\begin{cases}
a+1 & n=0\\
a & n=1\\
0 & n=2\\
\delta_{0a} & n=3\\
\delta_{0,\mod\left(a,2\right)} & n=4,5,\cdots
\end{cases}
\]
ハイバー演算子とクヌースの矢印表記の関係
\[
H_{n}\left(a,b\right)=a\uparrow^{n-2}b\;,\;n\in\mathbb{Z}
\]