設問6の解説:アッカーマンの呪い

CodeIQに投稿した問題6「アッカーマンの呪い」の解答を解説します。

問題

昔、アッカーマンという人(残念ながらミカサという妙齢の女性ではありません)がいました。
その人の手帳には以下のような式が書かれていました。

A(m, n) =
m = 0 ならば n + 1
n = 0 ならば A(m - 1, 1)
他の場合は A(m - 1, A(m, n - 1))

この関数を計算してみましょう。
A(1,3)の場合は以下のようになります。

 A(1,3)
=A(0,A(1,2))
=A(0,A(0,A(1,1)))
=A(0,A(0,A(0,A(1,0))))
=A(0,A(0,A(0,A(0,1))))
=A(0,A(0,A(0,2)))
=A(0,A(0,3))
=A(0,4)
=5

問1A
A(2,1)を手で計算してみましょう。
(解答を提出する必要はありません)

問1B
気力のある人はA(2,2)を手で計算してみましょう。
(解答を提出する必要はありません)

問2A
再帰関数を使ってプログラムを書いてみましょう。
プログラミング言語は問いません。

A(3,4) の値はいくつになりますか。
答えと使った言語名のみを書いて提出してください。
プログラムの提出は必要ありません。

問2B
A(4,1) をプログラムで計算してみましょう。
ただし、スタックオバーフローのエラーが出る恐れがありますので、
パラメータ値の増加には十分注意してください。
ハングアップする恐れがあるので、他の重要なプログラムが走っているときは実行するの
はやめたほうが良いです。
(もし値が計算できたら、3行目に答を書いてください)

【解答方法】
テキストファイルに以下のように解答を書いてください。
完成しましたら、ファイルアップロードより提出してください。

???   # 1 行目 問2Aの答え
???   # 2 行目 プログラミング言語名
???   # 3 行目 問2Bの答え(計算出来なかったら空欄でも構いません)

【補足】
A(4,1) は何とか計算できるかもしれませんが、
A(4,2) はあまりにも値が大きいので普通の方法では計算できないでしょう。

LISP等を使ったほうがすんなり行くかもしれません。

コンピュータを壊さないように気をつけて頑張ってください。

解説

今回の問題はWilhelm Friedrich Ackermannというドイツの数学者が考案したアッカーマン関数を問題としました。残念ながら、進撃の巨人とは何の関係もありません。(ただし、進撃の巨人の舞台がドイツらしいので関係なくはありませんが...)

手計算の結果は以下の通りです。何度も再帰的に計算しているが視覚的に分かるように省略せずに全過程を書いてみました。僅かな数なのに再帰が深くなっているのが分かるでしょうか。

問2.1

 A(2,1))
=A(1,A(2,0))
=A(1,A(1,1))
=A(1,A(0,A(1,0))
=A(1,A(0,A(0,1)))
=A(1,A(0,2))
=A(1,3)
=A(0,A(1,2))
=A(0,A(0,A(1,1)))
=A(0,A(0,A(0,A(1,0))))
=A(0,A(0,A(0,A(0,1))))
=A(0,A(0,A(0,2)))
=A(0,A(0,3))
=A(0,4)
=5 

問2.2

 A(2,2)
=A(1,A(2,1))
=A(1,A(1,A(2,0)))
=A(1,A(1,A(1,1)))
=A(1,A(1,A(0,A(1,0)))
=A(1,A(1,A(0,A(0,1))))
=A(1,A(1,A(0,2)))
=A(1,A(1,3))
=A(1,A(0,A(1,2)))
=A(1,A(0,A(0,A(1,1))))
=A(1,A(0,A(0,A(0,A(1,0)))))
=A(1,A(0,A(0,A(0,A(0,1)))))
=A(1,A(0,A(0,A(0,2))))
=A(1,A(0,A(0,3)))
=A(1,A(0,4))
=A(1,5)
=A(0,A(1,4))
=A(0,A(0,A(1,3)))
=A(0,A(0,A(0,A(1,2))))
=A(0,A(0,A(0,A(0,A(1,1)))))
=A(0,A(0,A(0,A(0,A(0,A(1,0))))))
=A(0,A(0,A(0,A(0,A(0,A(0,1))))))
=A(0,A(0,A(0,A(0,A(0,2)))))
=A(0,A(0,A(0,A(0,3))))
=A(0,A(0,A(0,4)))
=A(0,A(0,5))
=A(0,6)
=7

アッカーマン関数は、自分自身を値として取る再帰関数ですが、簡単な定義にも関わらず、最初の部分でさえ爆発的に大きな値が現れてしまいます。

Wikipedia:アッカーマン関数より転載

私が大学の夏期特別講座でこのアッカーマン関数を知りました。当時は、コンピュータは一般的には存在せず、共有の大型コンピュータをかろうじて使うことが出来ましたが、一行書くのに一回リターンキーを押してしまうと二、三分待たなければ、レスポンスが帰ってこないと言う有様でした。年がバレてしまいますがwww。

ですから、自分でこの関数をコンピュータでプログラミングするなんてできませんから、手で計算したのです。ところが、小さな値で計算を始めたにも関わらず、なかなか答えが収束せず、大変な思いをしました。その時、友人が書きすぎて手が痛くなったので、「これはアッカーマンの呪いだ!」と叫んでいました。そこで、これを今回の問題のタイトルにしたというわけです。

Pythonでのプログラミングの例

def ack(m, n):

    if m == 0:
        return n + 1
    if n == 0:
        return ack(m - 1, 1)
    else:
        return ack(m - 1, ack(m, n - 1))

###
print ack(3,4)

挑戦者のtakana32さんがいろいろな言語で書いたアッカーマン関数のプログラムを公開してくれたので、参考にしてください。
https://github.com/Rosetta-Ack

問2A
A(3,4)の答えは125。

問2B
A(4,1)の答えは65533となります。

既にA(4,1)でコンピュータがエラーを吐き出し始めるかと思います。私のUbuntuの場合、パラメータをいじったのですが、A(4,1)はスタックオーバーフローで計算できませんでした。

A(4,2)は 2^65536 – 3 になり、19729桁という膨大な数になってしまい、通常のやり方では計算不可能です。しかし、PythonRubyではintegerに収まらない数も扱えるため、既に計算した値を保持することで、A(4,2)等も計算することができます。

スタックオーバーフローの対処方法についてはいくつかありますので、参考にしてみてください。
スタックオーバーフローの対処方法

とにかく、こんな簡単な式でこんな爆発的に大きな数が作れるなんて不思議ですね。しかも、コンピュータの普及していない時代にこんな関数を考えだすなんて数学者ってすごいなと思います。

CodeIQで問題作成してますので、他の問題も挑戦してみてください。
https://codeiq.jp/ace/kawagashira_nobuyuki/