アッカーマン関数
マロ：前回の続きだよ！↓前回
アッカーマン関数について
このアッカーマン関数は名前の通りアッカーマンさんが作った関数なんだけど、アッカーマンさんが学生の時に考えた関数！
どんな経緯で作られたかはwikipediaに書かれてるから気になったら見てみてね！
元々のアッカーマン関数は三変数の関数だったんだけど、はじめは簡単な2変数アッカーマン関数についてやるね
2変数アッカーマン関数
2変数アッカーマン関数は次のように定義されるよ(m,nは0以上の整数)
$$
A(m,n)=
\left\{
\begin{array}{llc}
n+1 & \text{if}\ m=0 & (1)\\
A(m-1,1) & \text{if}\ n=0 & (2)\\
A(m-1,A(m,n-1)) & \text{if}\ m\not=0,\ n\not=0 & (3)
\end{array}
\right.
$$
この定義を見て間のいい人は気づくかもしれないけどめちゃくちゃ計算がだるそうだよね（笑）
実際めちゃくちゃだるくて、試しに$${A(3,2)}$$を計算してみると、
$$
\begin{array}{l}
A(3,2)\\
=A(2,A(3,1))\\
=A(2,A(2,A(3,0)))\\
=A(2,A(2,A(2,1)))\\
=A(2,A(2,A(1,A(2,0))))\\
=A(2,A(2,A(1,A(1,1))))\\
=A(2,A(2,A(1,A(0,A(1,0)))))\\
=A(2,A(2,A(1,A(0,A(0,1)))))\\
=A(2,A(2,A(1,A(0,2))))\\
=A(2,A(2,A(1,3)))\\
=A(2,A(2,A(0,A(1,2))))\\
=A(2,A(2,A(0,A(0,A(1,1)))))\\
=A(2,A(2,A(0,A(0,A(0,A(1,0))))))\\
=A(2,A(2,A(0,A(0,A(0,A(0,1))))))\\
=A(2,A(2,A(0,A(0,A(0,2)))))\\
=A(2,A(2,A(0,A(0,3))))\\
=A(2,A(2,A(0,4)))\\
=A(2,A(2,5))\\
\dots\\
=29
\end{array}
$$
こんな感じですごくだるい！さすがにマロも$${A(2,A(2,5))}$$からはやる気が起きなかった（笑）
(最後にこの計算の詳細を載せます。たくさんあります)
簡単に言えば、$${A(3,2)}$$の$${m}$$の部分が0になるまで、(1)~(3)の式を繰り返し使っていけばいいんだけど、なかなか1になってくれないんだよね（笑）
さっきの$${A(3,2)}$$を最後までやってやっと29って結果がわかるんだけど、実際手計算だと時間がかかりすぎるから、ここのサイトだと自動で計算してくれるよ！
でも注意なのが、ｍとかｎをデカくしすぎると計算しきれないぐらいデカい数字になっちゃうからね
ここで、前回説明したクヌースの矢印表記、コンウェイのチェーン表記、ハイパー演算子を使うと、(m$${\ge}$$3)
$$
\begin{array}{l}
\begin{array}{l}
A(m,n)\\
=(2\uparrow^{m-2}(n+3))-3\\
=(2\rightarrow(n+3)\rightarrow(m-2))-3\\
=\text{hyper}m(2,n+3)-3\\
\end{array}\\
\left(
\begin{array}{l}
=\text{hyper}(2,m,n+3)-3\\
=2^{(m)}(n+3)-3)
\end{array}
\right)
\end{array}
$$
それぞれから別の式の変形は前回のを見てもらえばわかるから、なんでアッカーマン関数がこんな関数になるかは考えてみて！
まあこの式に変形できたところで計算が楽になるわけじゃないけどね。
この式を見ればｍとかｎを大きくすると数字が大きくなるのがわかりやすくなるね
多変数アッカーマン関数
さっきまでは2変数アッカーマン関数だったけど、2ちゃんねるの巨大数探索スレッドで多変数アッカーマン関数が考えられて、
$$
\begin{array}{lll}
a,bは0以上の整数\\
Mは0個以上の0\\
Nは0個以上の0以上の整数\\
\\
A(M,a)&=a+1&(1)\\
A(N,a+1,0,M,b)&=A(N,a,b,M,b)&(2)\\
A(N,a+1,0)&= A(N,a,1)&(3)\\
A(N,a+1,b+1)&=A(N,a,A(N,a+1,b))&(4)
\end{array}
$$
一見難しくなったように見えるけど、よーく見てみると2変数アッカーマン関数と(1),(3),(4)が似てて、(2)が新しく追加されただけなんだよね
だからこそこの多変数アッカーマン関数はさらに計算がだるくなってて、しかも数字もさらにでかくなりやすいんだよね。
マロはやる気が全く起きないから時間がたくさんある人は適当に数字たくさん入れて計算してみたらわかるよ（笑）
少し脱線
ここで出てきた2ちゃんねるの巨大数探索スレッドなんだけど、このスレッドは半端じゃないんだよね
さっき出した多変数アッカーマン関数もだけど、ふぃっしゅっしゅさんっていう人が作ったふぃっしゅ数っていうのも化け物なんだよね（笑）
ここのサイトでバージョンごとにページを飛んでみればわかるんだけど、なかなか読むのも大変で、少し難しい内容になってるんだよね
だからマロが理解できて、かみ砕いて説明できるようになったら紹介するね！
まとめ
今回はアッカーマン関数について紹介したよ！
アッカーマン関数の定義は
$$
A(m,n)=
\left\{
\begin{array}{ll}
n+1 & \text{if}\ m=0\\
A(m-1,1) & \text{if}\ n=0 \\
A(m-1,A(m,n-1)) & \text{if}\ m\not=0,\ n\not=0
\end{array}
\right.
$$
だったね。
もし前回の今回のブログで巨大数に興味を持ったら、巨大数研究Wikiっていうサイトがあるからこっちを見るのもいいよ！
最後に
マロ：ちょっとだるい計算ばかりで疲れたかもだけどどうだった？
ミケ：結果がそこまで大きくなくてもこんなに地道な計算が必要ならパソコンにやらせたいね（笑）
マロ：実際にパソコンの性能テストで使われることもあるらしいよ！
ミケ：へえ～。自分のでするとフリーズしそう（笑）
マロ：ミケのがフリーズするならマロのは起動できなくなっちゃうよ（笑）
参考サイト
A(3,2)の途中式
ここに乗せる途中式はプログラムを組んで計算しました。
もしこれからアッカーマン関数を手計算でしようとしている人はこの量になるかもしれないという覚悟を持ってください。
パソコンで見ることをお勧めします。
ここまで読んでいただきありがとうごさいます。
感想、指摘、リクエストなど気軽にコメントしてください！
byマロ
この記事が気に入ったらサポートをしてみませんか？