加法から始める巨大数・後編（上） クヌースの矢印表記, アッカーマン関数
前回はこちら。
前回までは巨大数詐欺だったので、今回からしっかり巨大数を紹介していきます。まずは既に登場したクヌースの矢印表記について話します。クヌースの矢印表記とは、ハイパー演算子と次のような関係にありました。
つまり、a↑b は馴染みのある冪のことであり、a↑↑b はこのシリーズで扱ってきたテトレーションを表します。しかし、テトレーションはハイパー演算子の４番目に過ぎません。つまり、５番目以降も考えることができ、次のように定義されます。
これをペンテーションといいます。重なる指数の数がえらいことにことになってることから、テトレーションよりもずっと大きい値を返すような関数だと分かります。（右から計算することに注意してください。）そして、クヌースの矢印表記を用いると次のように表されます。
では、実際に計算をしてみましょう。
参考にテトレーションは 2↑↑4=65536、 2↑↑5=2↑65536(=2↑2↑2↑2↑2) となります。2↑↑↑3 までは大して変わらないように感じますが、2↑↑↑4 以降は比べ物にならないくらい大きくなることが分かります。
しかしこれでも５番目のハイパー演算子。６番目になると、さらに凶悪です。
クヌースの矢印表記は当然、上矢印が一本増えて a↑↑↑↑b となっています。これをヘキセーションといいます。計算例も挙げておきます。
今度は 2↑↑↑↑3 から既にエグい数字になりました。2↑↑↑↑4 も書こうかと思いましたが、これがこれ以上計算できない以上、2↑↑↑↑4=2↑↑↑(2↑↑65536) と書くしかないので省略しました。とにかくエグいことは分かったと思います。
しかし、この先にはさらに７番目、８番目…と続いていきます。名前は恐らくヘプテーション、オクテーション…となるのでしょう。
ただ、今のクヌースの矢印表記には弱点が１つあります。それは ↑ を書く（または数える）のが大変だということです。しかし、これも簡単に解決できます。
次のように、↑ の個数を添えることにするのです。
これにより、例えば a↑↑...(100個の↑)…↑b なんていうトンデモナイ演算（ヘクテーションとでもいうのだろうか。 [追記(2021/02/16)] 違いました。ヘクテーションはH₁₀₀(a,b) なので、クヌースの矢印表記では a↑⁹⁸b です。）も a↑¹⁰⁰b と書くだけで表せてしまいます。
[追記(2021/02/16)] ちなみに n がどんな値であっても、2(↑^n)2=4 となります。これは数学的帰納法で簡単に示せます。
さて、今回はもう一つ紹介します。それはアッカーマン関数と呼ばれるものです。定義は次の通り。
なんじゃこりゃーとなりますが、実際に計算してみたら慣れてくると思います。ただ、m,n の値は慎重に選ばないとなりません。
実はこの関数、大きさとしてはクヌースの矢印表記と大して変わらないのですが、計算量がひどく多いのが特徴なのです。実際に Ack(2,2) を計算した例を紹介します。
こんだけ計算して値はたったの 7 かよ、って感じですが、適当に変数を選ぶとちゃんと大きい値がでます。その場合、計算量も人の手では書けないくらい膨大になりますが…。
そしてクヌースの矢印表記と同じくらいの大きさだと言いましたが、実際、次のような等式が成り立ちます。
クヌースの矢印表記で表せるのは m≧3 のときとしていますが、↑⁰ を無理やり乗法と解釈してあげれば実際に Ack(2,2)=2×(2+3)-3=7 となることが確かめられます。
ちなみに、アッカーマン関数を拡張した多変数アッカーマン関数というものもあり、それはクヌースの矢印表記や次回紹介するコンウェイのチェーン表記よりもずっと大きい数を表すことができます。ただ、僕自身が理解ができていないため、今回は存在の紹介に留めます。理解できたら、いつか記事にするかもです。
今回の内容は以上です。前中後の３編で構成するつもりでしたが、後編が意外と書きたいことが多かったので、さらに上下に分けることにしました。次回はさらに巨大な数を２つ紹介します。ではまた。
