タワー表記とグラハム数

過去ブログの転載です。

タワー表記

を
を

というように、新しい演算子を使って演算を拡張することができますが、実はその更に上もきちんと用意されています。表現方法は色々あるのですが、ここではタワー表記（クヌースの矢印表記）を紹介します。

タワー表記では、のことを、と表現するのです。矢印記号2つ重ねたものですね。

という巨大な数になっちまいます。

何で矢印記号を2つ重ねたものとして表現するかというと、普通の累乗を矢印記号1つとしても表現できる、としたためです。例えばは、タワー表記ではとも表現してよいものとします。はと表せる、ということですね。矢印の処理自体は累乗と同じなので、右側にあるものから計算していきます。

PCでよく累乗の記号として「＾」が使用されますが、これは実はこのタワー表記でいう累乗記号「」にちなむという噂です。

矢印の個数が大きい演算子を展開すると、矢印が1個減った演算子になるという具合ですね。 ということです。

この調子で、矢印3個とかも定義できることになります。矢印3個は、矢印2個を拡張した演算子ということになります。

であれば、これはと同じという意味になりますね。

一般に、矢印個の演算結果は、矢印個を並べたもの、となります。ちょっと↑この式を途中まで計算してみましょう。

ホラ、もうでかすぎて、これ以上計算できないですね！

このように、タワー表記は被演算子の数値をちょっと大きくしただけで、爆発的に巨大な数に化ける性質があります。

グラハム数

グラハム数とはギネスブックにも載った巨大数です。「証明に使われたことのある、最も大きな数」ということで紹介されたようです。あまりに大きすぎて、その桁数を表現することすら絶対無理という数です。どんな証明問題かはちょっと難しいので割愛します。

これを表現するのに、先ほどのタワー表記が使用されます。タワー表記を次のように表現出来るようにしておきます：

矢印の個数を、肩に載せた数字で表現するのです。もうすでに↑コレが巨大数であることはすぐわかりますね。試しに途中まで計算してみると、

もう無理ですね……こんな序盤で巨大数になってしまいましたから、だけ見るとどれぐらい巨大な数か、なんとなくイメージがつくと思います。

でも、グラハム数の大きさはこんなものではありません。グラハム数からすれば、ですら目に見えないぐらい小さな数です。

ここで、次のような関数を定義します：

なんと、矢印の個数を変数にしてしまった関数です。例えばとなります。ヤバイですね。

更に何をやりたいかというと、このえげつないを入れ子にしてしまうのです。といった具合です。

ということですね。矢印の個数ですら巨大数になってしまいました。

こんなものを定義した上で、グラハム数とはどんな数かというと、↓こんな数なんですよ＠＿＠

グラハム数＝

どんなことが起こっているか、もう大体分かるでしょう。が64回入れ子になってます。単なる巨大と言い切ることもできないぐらい巨大な数ということがわかると思います。ヤバイでしょ、ヤバイよねぇ。

巨大数って意外と難しく、それがどれぐらい巨大なのか、なかなか直観的にイメージすることも難しいようなものがほとんどです。その中でもグラハム数は、タワー表記のイメージさえ出来ていれば、割と容易に巨大性に気づけるので、わああぁ！と思いやすいのが面白い所だと思います。何の話や……