Ackermann関数
今回は、完全に高校の授業とは関係ない私が学生だった頃の思い出話です。
プログラム作成のきっかけ
プログラミング言語演習だったか計算機科学の科目だったか忘れてしまいましたがの講義で、アッカーマン関数という関数の話がありました。関数の紹介は次節でお示ししますが、引数が2つある再帰関数です。これが厄介な関数で、ものすごく大きな値になるにも関わらず、再帰が深くなるか、＋１されるかしかないという恐ろしい関数です。担当の先生が「Ack(4,2)の値を正確に求めるプログラムを書いてレポートを出したら、単位を出す」ということを話されました。「そんなので単位がもらえるならラッキー♪」とチャレンジしました。といってももう四半世紀以上前のことなので、記憶はかなりあやふやです(´・ω・｀)
Ackermann関数
Ackermann関数（アッカーマン関数）は次の式で定義されます。
\[
Ack(m,n) = \begin{cases}
n+1 & (m=0) \\
Ack(m-1,1) & (n=0) \\
Ack(m-1,Ack(m,n-1)) & (otherwise)
\end{cases}
\]
そして、計算結果はとっくに忘れているのでググったら
\[
Ack(4,2) = 2^{65536}-3
\]
と出ました。こんな数だったんですね。もちろん、指数で表すことなく、多倍長整数で正確な値を出すというものです。
その後
どれくらい大変だったか忘れましたが、忘れてしまう程度の難易度でプログラムを書いて提出し、単位をもらいました。レポート提出後に講義にちゃんと出ていたかどうかすら忘れました。他の講義も出たり出なかったりしていたいい加減な学生だったので・・・すみません_(._.)_
大学卒業後約２０年経った頃、教育センターでの研修会に参加したら、なんと！その科目を担当されていた先生が講師でした。名刺交換しながらおそるおそるその時の話をしたら、その当時のことを覚えていらっしゃいました。私以外にも何人かレポートを書いて単位をもらっていたとのことです。ちゃんと出席していたかどうか怪しい学生のことを覚えていたことは、本当に驚きました。
以上で今回はおしまいです。え？プログラム？がんばって書いてください。答えは\(Ack(4,2) = 2^{65536}-3\)だってことはわかっているんだから。
ではまた次回お会いしましょう。（気が向いたらそのうちプログラムをアップするかもしれません）
次回からは学期中になるので、更新頻度が下がりますが、引き続きよろしくお願いします。