アッカーマン関数をpythonで書いたら瞬殺できた話。




スポンサードリンク

アッカーマン関数とは

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

アッカーマン関数の定義を以下に示します。
\[
\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=0〜3、n=0〜4の時の計算結果を3次元散布図でプロットして見ました。

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

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

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

wikipedia参照

 

A(3,1)では13なのにA(4,1)では、65533になっています。nの増加率は2nとそんな変わらないですが、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}
なんだかゲシュタルト崩壊でも起こしそうですね。



スポンサードリンク



スポンサードリンク

記事が役に立ったらシェア!

投稿者:

中村 俊

中村 俊

1993/09/04生まれ。機械系大学院を休学し、ベンチャーでインターンしている最中。直近では、デカルトの「方法序説」に感銘を受けた。 趣味:読書、web開発の勉強、異分野の論文読んだり、記事書いたり。 最終的には経営者か研究者になりたい。

「アッカーマン関数をpythonで書いたら瞬殺できた話。」への2件のフィードバック

  1. とても面白い記事ですね。どうすれば私からも見れるようになるでしょうか。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

CAPTCHA