加法から始める巨大数・後編(下) コンウェイのチェーン表記, 4変数BEAF
前回はこちら。
今回は前回紹介したクヌースの矢印表記やアッカーマン関数よりも強い表記法・関数を紹介します。
最初に紹介するのはコンウェイのチェーン表記と呼ばれるもので、次のようなものです。
(1)' は a→b→1 の →1 を省略していると解釈すればよいと思います。なお、定義としては(1)と(1)'のどちらか一方だけ採用すればよいそうです。
しかし、これだけだと本質的にクヌースの矢印表記と変わりません。ここからがチェーン表記の強いところで、「チェーン」というだけあって4つ以上の自然数を → を介して繋ぐことができるのです。そしてその場合、次のように定義されます。
(2)と(2)'は途中に 1 があれば、それ自身と(もし続きがあるならば)1 以降のチェーンを消去できることを表しています。そして(3)はやや複雑ですが、ここまでのどれにも当てはまらない場合、最後尾の数字を 1 減らし、最後尾から二番目の数字を「最後尾から二番目の数字を 1 減らしたチェーン全体」に置き換えます。
計算例を見てみましょう。
3→2→2→2 はまだクヌースの矢印表記で表されますが、チェーンを一つ伸ばした 3→2→2→2→2 はもはやクヌースの矢印表記では表せません。便宜上 M₂₅ という文字をおいてますが、これは M₂₄ を含むチェーンから巨大数であり、M₂₄ も…といった具合なので、クヌースの矢印表記やアッカーマン関数と比較できないほど大きいことが分かります。
ただ、チェーンを長くするほど爆発的に大きくなることは分かりましたが、長く伸ばすには広いスペースが必要になります。そのため cg(n) を次の定義することで、この問題も解決できます。計算例として cg(3) も載せておきます。
非常に大きいコンウェイのチェーン表記ですが、これは拡張することでさらに強力にすることができます。拡張には二通りあるようですが、今回はピーター・ハーウォード氏によるものを紹介します。
僕も始め混乱したので注意しなければなりませんが、これはチェーンの長さ(変数の数)が2になったときにはじめて成り立ちます。長さが3以上のときは → の下付き文字を無視して、拡張前と同様に計算します。
計算例を載せておきます。とはいえ、大きすぎて途中までしか計算できませんが…。
赤と紫の部分で、→ の下付き文字が効力を発揮しています。コンウェイのチェーン表きですら表せないことからも、一段階上の巨大数であることが分かります。
しかし、今回はこれよりもさらに強力な関数を紹介します。それはBEAFと呼ばれるものです。beef みたいで変わった名前ですが、Bowers Exploding Array Function の頭文字をとっているようです。(日本語訳するなら「バウアーズの爆発配列関数」でしょうか?)
a{c}b=a(↑^c)b というのが BEAF の基本的な定義ですが、それではクヌースの矢印表記と変わらない。そこで {} を二重にすることで (2.1) のように定義し、爆発させることができます。
しかし、二重ができるなら三重以降も存在します。
そして、d重のとき (3) のように表記し、そのとき (2.1),(2.2) は (2) のように一般化できます。
3重以上の BEAF に関しては非常に大きいことは分かると思うので、ゴチャゴチャするし省略します。
また、これらは次のように定義することで {a,b,c,d} とシンプルにまとめることができます。
以上で書きたいことは大体書きましたが、BEAF の本領はまだまだこんなものではありません。{a,b,c,d} はコンウェイのチェーン表記に似た定義により、5 個以上の変数 {a,b,c,...,y,z} に拡張することができます。このような表記は線形配列と呼ばれるもので、前回存在だけ紹介した多変数アッカーマン関数と同程度になります。
しかし、BEAF はまだまだこんなものでは終わりません。さらに多次元配列、テトレーション配列と、より強力な表記が存在します。ここまでくると、もはや多変数アッカーマン関数すら超えてきます。実はこれより先の表記もあるようですが、その定義はまだ不完全と言われていますが、もし適切に定義されればここまで紹介してきたものとも比較できないほど大きくなるそうです。
ちなみに、あるサイトでは巨大数をランク分けとして、指数を重ねる表記(10^10^10^10 など)の上に、「テトレーション」「矢印表記」「チェーン表記」「多変数アッカーマン」のようにランク分けされているようです。当然、その上のランクも存在するようで有名な例としては「ふぃっしゅ数バージョン3」があります。
ここまで長々と巨大数の紹介をしてきて今更ですが、僕もしっかりと勉強したわけではないです。そのため様々なサイトを参考にしたので、それらを紹介して終わりにします。
他にもWikipediaやaster氏のニコニコ動画の解説動画も参考にしました。
これより先も個人的に勉強すると思いますが、不正確な情報を提供する可能性も高い(ここまでの正確性も不明ですが…)ので、ブログにはかかないんじゃないかなーと思います。
以上で「加法から始める巨大数」は終了します。次回も理解してるとは言えないような知識の紹介になりますが、「ガンマ関数」のようなもう少し有名な話題を扱っていこうと思います。ではまた。