お知らせ

ただいま、シンタックスハイライターの設定を見直しております。
プログラムが見にくくなっているページがありますが、ご容赦ください。

Ackermann関数

プログラミング

数字の羅列

今回は、完全に高校の授業とは関係ない私が学生だった頃の思い出話です。

プログラム作成のきっかけ

プログラミング言語演習だったか計算機科学の科目だったか忘れてしまいましたがの講義で、アッカーマン関数という関数の話がありました。関数の紹介は次節でお示ししますが、引数が2つある再帰関数です。これが厄介な関数で、ものすごく大きな値になるにも関わらず、再帰が深くなるか、+1されるかしかないという恐ろしい関数です。担当の先生が「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
\]

と出ました。こんな数だったんですね。もちろん、指数で表すことなく、多倍長整数で正確な値を出すというものです。

その後

どれくらい大変だったか忘れましたが、忘れてしまう程度の難易度でプログラムを書いて提出し、単位をもらいました。レポート提出後に講義にちゃんと出ていたかどうかすら忘れました。他の講義も出たり出なかったりしていたいい加減な学生だったので・・・すみません_(._.)_

大学卒業後約20年経った頃、教育センターでの研修会に参加したら、なんと!その科目を担当されていた先生が講師でした。名刺交換しながらおそるおそるその時の話をしたら、その当時のことを覚えていらっしゃいました。私以外にも何人かレポートを書いて単位をもらっていたとのことです。ちゃんと出席していたかどうか怪しい学生のことを覚えていたことは、本当に驚きました。

以上で今回はおしまいです。え?プログラム?がんばって書いてください。答えは\(Ack(4,2) = 2^{65536}-3\)だってことはわかっているんだから。

ではまた次回お会いしましょう。(気が向いたらそのうちプログラムをアップするかもしれません)

次回からは学期中になるので、更新頻度が下がりますが、引き続きよろしくお願いします。

この記事を書いた人
春日井 優

高校で情報科という教科を担当しています。以前は数学科も担当していました。(今でも数学科の教員免許状は有効です。)プログラムを覚えたのは、「ゲームセンターあらし」という漫画のキャラクターがBASICを解説する「こんにちはマイコン」を読んだことがきっかけでした。

Posted by kasugai