アッカーマン関数とは

先日、アッカーマン関数というものを初めて知ったので、それについて書いていきます。なんかのアニメのキャラを連想しますが笑

アッカーマン関数の定義を以下に示します。
\[
\mathrm{Ack}(m,n)=
\left\{
\begin{array}{ll}
n+1 , (m=0)\\
\mathrm{Ack}(m-1,1), (n=0)\\
\mathrm{Ack}(m-1,\mathrm{Ack}(m,n-1)) ,(m\neq n\neq 0)
\end{array}
\right.
\]

関数の中に、自身の関数が含まれますので再帰関数ということになります。計算自体はそんなに難しくありませんが、根気が必要です。というよりこのタイプの関数はプログラム書いた方が、早いですよね。

ついでに手計算するとこんな感じになります。

即興感満載で申し訳ないですが、だらだらと地道にやるだけです。難しい計算もないです。中学生、いや足し算と引き算しか使っていないので小学生でもできます。

ですが、pythonで書いたら一瞬でした。さすが関数型の言語というところでしょうか。

 

特徴

この関数の特徴は「解の発散性」にあります。試しにm=０〜３、n=０〜４の時の計算結果を３次元散布図でプロットして見ました。

少しわかりづらいので、違う角度から。

指数関数とも少し違う増加傾向がありますね。今、mを３までしか計算してませんが、m＝４にすると、pythonが

”RuntimeError: maximum recursion depth exceeded ”とか言ってきます。数がでかすぎて計算できねぇよって。ウソーンと思ってちょっと調べると、

 

A(3,1)では13なのにA(4,1)では、65533になっています。nの増加率は2ⁿとそんな変わらないですが、mの増加率はえぐいことになってます。この増加傾向がアッカーマン関数の特徴と言えるでしょう（適当笑）

スポンサードリンク

この関数何に使うの？

問題はそこです。こんなでかすぎる関数何に使うんだよって感じですが、グラフ理論でグラフの計量評価に使ったりするらしい（意味不）。他にも、単純な計算手続きというのを利用して、いろんな言語でこのプログラムを書いて、どの言語が一番早いのか試した人もいるそう（ついでにpythonはクソ遅いww）。

関数が定義されているくらいなので、使っている研究者は腐る程いるんでしょう。ついでに考案したのはドイツの数学者の「ヴィルヘルム・アッカーマン」という人。よくこんな関数思いつきますよね。

ついでに進撃のなんちゃらはドイツのどこかの町がモデルになってるみたいですが、何か関係あるかもですね。

最後に

2問だけ問題と回答を載せます。
\begin{eqnarray}
\mathrm{Ack}(1,1)
&=&\mathrm{Ack}(0,\mathrm{Ack}(1,0))\\
&=&\mathrm{Ack}(0,\mathrm{Ack}(0,1))\\
&=&\mathrm{Ack}(0,2)\\
&=&3
\end{eqnarray}
\begin{eqnarray}
\mathrm{Ack}(2,1)&=&\mathrm{Ack}(1,\mathrm{Ack}(2,0))\\
&=&\mathrm{Ack}(1,\mathrm{Ack}(1,1))\\
&=&\mathrm{Ack}(1,\mathrm{Ack}(0,\mathrm{Ack}(1,0)))\\
&=&\mathrm{Ack}(1,\mathrm{Ack}(0,\mathrm{Ack}(0,1)))\\
&=&\mathrm{Ack}(1,\mathrm{Ack}(0,2))\\
&=&\mathrm{Ack}(1,3)\\
&=&\mathrm{Ack}(0,\mathrm{Ack}(1,2))\\
&=&\mathrm{Ack}(0,\mathrm{Ack}(0,\mathrm{Ack}(1,1)))\\
&=&\mathrm{Ack}(0,\mathrm{Ack}(0,\mathrm{Ack}(0,2)))\\
&=&\mathrm{Ack}(0,\mathrm{Ack}(0,3))\\
&=&\mathrm{Ack}(0,4)\\
&=&5
\end{eqnarray}
なんだかゲシュタルト崩壊でも起こしそうですね。

スポンサードリンク

スポンサードリンク