今日の実験ノート

今日やったことを気ままに綴るノート。

Tag: math

巨大数の世界〜グラハム数の評価〜

概要

巨大数とは、日常生活では使用しないほど大きな数のことである。 定義は曖昧で、この分野の存在意義は各自に任せるが、この 途方もない数の爆発 に言いようもない魅力を感じるのは間違いない。

途方もない巨大数を生み出したときに、その巨大数はどれほどの大きさなのか「評価」したいという欲求を満たすため、 さらなる巨大数を生み出してしまう。

(数の評価をするということは、その数を 不等号により評価 するということであり、巨大数の評価のために より「強い」 巨大数を生み出す必要がある。)

またこれらの記事はAeton氏によって投稿された、【ゆっくりと学ぶ】グラハム数を解説してみた【再UP版】と、 この動画の中で言及されているふぃっしゅっしゅ氏による巨大数論、有志による巨大数研究 Wikiに大きな影響を受けていることを記述して、先人の研究に感謝したいと思う。

巨大数の導入

「巨大数」と言われてどんな数を想像しただろうか。

とりあえず、こんな数だろうか。

$latex 9999999999 $

しかし私はこの横にこんな数を書いて、この数より大きな数を書いてしまう。

$latex 9999999999 \ll 10^{20} $

この議論は巨大数の世界を最も象徴している。

$latex 9999999999$ という数は把握しにくい数だが、 $latex 10^{20}$ という数より小さいことがわかる。

$latex 10^{20}$ という数は $latex 9999999999$ よりは把握しやすいため、これをもって $latex 9999999999$ という巨大数を把握したことになるのだ。

この記事の目標は「 グラハム数 」という巨大数の代表を評価することである。この「グラハム数」は数学の証明に使われた最大の数としてギネスブックに登録されている。

グラハム数の定義

グラハム数の導かれた過程は扱わない。頭が固い人によって書かれた記事などを参考にするといいだろう。

グラハム数 $LATEX G$ を次のとおりに定義する。

\begin{align} g(n) \triangleq 3 \uparrow ^n 3\\ G \triangleq g^{64}(4) \end{align}

この数を評価するのだが、そもそもが知らない記号がたくさん出ているため、1つずつ解説していきたい。

記法

クヌースの矢印表記

まず既存の記法から捉えなおそう。既存のルールと整合性を守って数を拡張するためには、既存のルールの把握は必要不可欠である。

わかりやすいところから、「冪乗」から議論を始める。 冪乗は 掛け算の繰り返し として捉えることが出来る。

$latex a^b \triangleq \underbrace{a\cdot a \cdot \dots \cdot a}_{b\qq[times]} $

とするとすれば、掛け算は 足し算の繰り返し になり、足し算は「1増やす」という 単項演算の繰り返し として捉えることが出来る。

単項演算子の $latex +$ と二項演算子の $latex +$ は異なる ことに注意しなければならない。

\begin{align} a+ &\triangleq a\text{の次の数}\\ a+b &\triangleq ((((a\underbrace{+)+)\dots)+)}_{b\qq[times]}\\ a\cdot b &\triangleq \underbrace{a+a+\dots+a}_{b\qq[times]}\\ a\verb|^|b = a^b &\triangleq \underbrace{a\cdot a\cdot\dots\cdot a}_{b\qq[times]}\\ \end{align}

こういうふうに捉え直すことで、冪乗を繰り返す演算である「 超冪乗 」なるものを考えることが出来る。ハットの記号を援用して次のように定義する。

$latex a\verb|^^|b \triangleq \underbrace{a\verb|^| a\verb|^| \dots \verb|^| a}_{b\qq[times]} =\underbrace{a^{a^{{}^{.\,^{.\,^{.\,^a}}}}}}_{b\qq[times]}$

超冪乗についてはこれまでの演算と異なり、 結合順により計算結果が異なってしまう。 右から左に向かって計算する( 右結合 )ことになっているので注意したい。 (式 $latex \ref{ne}$ は誤っている!)

\begin{align} 3\verb|^^|3 &\ne ((3\verb|^|3)\verb|^|3) = 27\verb|^|3 = 19683\label{ne}\\ 3\verb|^^|3 &= (3\verb|^|(3\verb|^|3)) = 3\verb|^|27 = 7625597484987 \end{align}

実際に紙に書いてみると分かるが、ハットを横に書き並べる記法はとても書きづらい。そのためハットの頂点から線を出し、(都合、上矢印となるが、)も使用して良いことにする。

これが クヌースの矢印表記 である。拡張して、n本の矢印も扱うことも出来る。 n本の矢印はn-1本の矢印に展開され、最終的に一本の矢印(冪乗)に展開される。

\begin{align} a^b = a\uparrow b &\triangleq \underbrace{a\cdot a\cdot\dots\cdot a}_{b\qq[times]}\\ a\uparrow\uparrow b &\triangleq \underbrace{a\uparrow a\uparrow\dots\uparrow a}_{b\qq[times]}\\ a\uparrow^n b &\triangleq a \underbrace{\uparrow\cdots\uparrow}_{b\qq{times}} a = \underbrace{a\uparrow^{n-1}a\uparrow^{n-1}\dots\uparrow^{n-1}a}_{b\qq[times]} \end{align}

ここで、面白い性質を紹介する。 $latex 2 \uparrow^n 2$ の場合だ。例として $latex 2 \uparrow^4 2$ を扱う。

\begin{align} 2 \uparrow\uparrow\uparrow\uparrow 2 &= \underbrace{2 \uparrow\uparrow\uparrow 2}_{2\qq[times]}\\ &= \underbrace{2 \uparrow\uparrow 2}_{2\qq[times]}\\ &= \underbrace{2 \uparrow 2}_{2\qq[times]}\\ &= 2^2 = 4 \end{align}

つまり、矢印が何本重なっても 最終的に $latex 2^2$ になってしまう ということだ。このため、クヌースの矢印表記では最も基本的な数として、3を扱うことに注意したい。

3の場合、無事に(?)数の爆発が発生する。

\begin{align} 3 \uparrow 3 &= 3^3 = 27\\\\ 3 \uparrow\uparrow 3 &= \underbrace{3 \uparrow (3 \uparrow 3)}_{3\qq[times]}\\ &= 3^{27} = 7625597484987 \simeq 7 \cdot 10^{12}\\\\ 3 \uparrow\uparrow\uparrow 3 &= \underbrace{3 \uparrow\uparrow (3 \uparrow\uparrow 3)}_{3\qq[times]}\\ &= \underbrace{3 \uparrow 3 \uparrow \cdots \uparrow 3}_{3 \uparrow\uparrow 3\qq[times]} = \underbrace{3 \uparrow 3 \uparrow \cdots \uparrow 3}_{7625597484987\qq[times]}\\\\ g(4) = 3 \uparrow\uparrow\uparrow\uparrow 3 &= \underbrace{3 \uparrow\uparrow\uparrow (3 \uparrow\uparrow\uparrow 3)}_{3\qq[times]}\\ &= \underbrace{3 \uparrow\uparrow 3 \uparrow\uparrow \cdots \uparrow\uparrow 3}_{3 \uparrow\uparrow\uparrow 3\qq[times]}\\ &= \underbrace{3 \uparrow 3 \uparrow \cdots \uparrow 3} _{\underbrace{3 \uparrow\uparrow 3 \uparrow\uparrow \cdots \uparrow\uparrow 3}_{3 \uparrow\uparrow\uparrow 3\qq[times]}} \end{align}

そしてようやくグラハム数に関連する $latex g(4)$ を説明することが出来た。「こんな途方もない数。。。」と思うかもしれない。

しかし例えば、私たちは $latex 3^{100}$ という数を正確に認識できているのだろうか。「ああ、 3を100回掛けた数 ね」という風に認識するだけではないだろうか。

$latex g(4)$ もこういう捉え方が出来ないだろうか。数を正確に捉えようとするのではなく、数の 生成方法 を味わうと言うだろうか。。。おっと駄文はこのくらいにしておこう。

合成関数

高校の数学でこのような定義を習ったことを覚えているだろうか。

$latex f^m(x) = (\underbrace{f \circ f \circ\dots\circ f}_{m\qq[times]}) = \underbrace{f(f(\dots(f}_{m\qq[times]}(x))))$

ここで、 $latex f^m(x)$ という記法には表記ゆれがあるため合成関数なのか、ただの関数値の冪乗なのかは文章の前後から読み取る必要がある。

グラハム数の定義に用いる、 $latex g^{64}(4)$ に関しては合成関数となる。

合成関数を簡単に復習する。

\begin{align} f(x) &\triangleq x^2+1\\\\ f^2(x) = f(f(x)) &= f(x^2+1)\\ &= (x^2+1)^2 + 1\\ &= x^4+2x^2+2\\\\ f^3(x) = f(f(f(x))) &= f(f(x^2+1))\\ &= f(x^4+2x+2)\\ &= (x^4+2x+2)^2 + 1\\ &= x^8 + 4x^6 + 8x^4 + 8x^2 + 5 \end{align}

という風に関数の結果を関数に渡すことで、簡単に関数を複雑にすることが出来る。

グラハム数に戻ると、

\begin{align} g(4) &\triangleq 3 \uparrow\uparrow\uparrow\uparrow 3\\\\ g^2(4) = g(g(4)) &= g(3 \uparrow\uparrow\uparrow\uparrow 3)\\ &= \left. \begin{matrix} 3 \underbrace{\uparrow\uparrow \cdots\cdots \uparrow} 3\\ 3 \uparrow\uparrow\uparrow\uparrow 3 \end{matrix} \right\}2\qq[layers]\\\\ g^3(4) = g(g(g(4))) &= g(g(3 \uparrow\uparrow\uparrow\uparrow 3))\\ &= g(3\underbrace{\uparrow\cdots\uparrow}_{3 \uparrow\uparrow\uparrow\uparrow 3} 3)\\ &= \left. \begin{matrix} 3 \underbrace{\uparrow\uparrow \cdots\cdots\cdots \uparrow} 3\\ 3 \underbrace{\uparrow\uparrow \cdots\cdots \uparrow} 3\\ 3 \uparrow\uparrow\uparrow\uparrow 3 \end{matrix} \right\}3\qq[layers]\\\\ g^4(4) = g(g(g(g(4)))) &= g(3 \underbrace{\uparrow\cdots\uparrow} _{3 \underbrace{\uparrow\cdots\uparrow} _{3 \uparrow\uparrow\uparrow\uparrow 3} 3} 3)\\ &= \left. \begin{matrix} 3 \underbrace{\uparrow\uparrow \cdots\cdots\cdots\cdots \uparrow} 3\\ 3 \underbrace{\uparrow\uparrow \cdots\cdots\cdots \uparrow} 3\\ 3 \underbrace{\uparrow\uparrow \cdots\cdots \uparrow} 3\\ 3 \uparrow\uparrow\uparrow\uparrow 3 \end{matrix} \right\}4\qq[layers] \end{align}

つまり、 $latex g(x)$ を繰り返すたびに一段ずつ深くなっているのだ。

注意するべきなのは、 $latex g(x)$ の繰り返しによって、 クヌースの矢印が 増えていっているため、それはそれは膨大な数になっている。

これでグラハム数の定義に戻ってみよう。

もう一度グラハム数

グラハム数の定義は次のとおりであった。

\begin{align} g(n) \triangleq 3 \uparrow ^n 3\\ G \triangleq g^{64}(4) \end{align}

g(4)の合成関数については既に考察を終えているので、つまり書き下すとこのようになる。

\begin{align} G = \left. \begin{matrix} 3 \underbrace{\uparrow\uparrow \cdots\cdots\cdots\cdots\cdots \uparrow} 3\\ 3 \underbrace{\uparrow\uparrow \cdots\cdots\cdots\cdots \uparrow} 3\\ \underbrace{\quad\quad \vdots \quad\quad}\\ 3 \underbrace{\uparrow\uparrow \cdots\cdots \uparrow} 3\\ 3 \uparrow\uparrow\uparrow\uparrow 3 \end{matrix} \right\}64\qq[layers] \end{align}

簡単に書いているが、この数は膨大な数である。例えば、 $LATEX G$ の最上段における 矢印の数が $latex g^{63}(4)$ 本ということからもその膨大さが伺えるだろう。

\begin{align} G = \left. \begin{matrix} 3 \overbrace{ \underbrace{\uparrow\uparrow \cdots\cdots\cdots\cdots\cdots \uparrow} }^{g^{63}(4)} 3\\ 3 \underbrace{\uparrow\uparrow \cdots\cdots\cdots\cdots \uparrow} 3\\ \underbrace{\quad\quad \vdots \quad\quad}\\ 3 \underbrace{\uparrow\uparrow \cdots\cdots \uparrow} 3\\ 3 \uparrow\uparrow\uparrow\uparrow 3 \end{matrix} \right\}64\qq[layers] \end{align}

指数関数の導入

概要

指数関数は微分において便利な性質を持っており、その応用範囲も広い。

まず、指数関数を自然数において導入し、指数の範囲を徐々に広げていく。

Continue reading