読者です 読者をやめる 読者になる 読者になる

けんぼーは留年生

Twitterに書ききれないこととか

より大きな数を!そこに意味はないが理由はある!(巨大数の話)~急増加関数編~

数学とか科学とか技術とか 大きな話

タイトルはhttp://urasunday.com/u-2_09/index.htmlの第四話より。

プロローグ

今まで僕は何度も巨大数に関する記事を書いてき…………てませんね。いや、書こうとは思ってたんですけどまだ1つしか書いてないですね。今書いたんでこれで許してください。

プロローグ

仕切り直し。
僕はまだ記事にしていないけど世の中には色んな巨大数やそれを作るための関数がある。例えばグラハム数とかアッカーマン関数とか僕が以前記事にしたコンウェイのチェーン表記とか。じゃあ、これらのあまりにも大きすぎる数や関数を比較するには如何にしよう? もちろん普通に十進表記していたら宇宙中の物質を紙にしても無理だし、指数表記を持ち込んだところで焼け石に水だ。僕たちが普段使う"ものさし"よりもはるかに巨大な化け物を比較するにはどうしたら良いか。答えは簡単、化け物みたいな"ものさし"を作れば良い。一定の感覚で目盛りがついていてとても大きなものまで測れる巨大ものさしを作るのだ。

というわけでよく巨大数の比較に使われる「急増加関数」というものを紹介していく。「急増加関数」は先述の「化け物みたいなものさし」に相当する。他の巨大数を生み出す諸関数に引けを取らないレベルで巨大な数を生み出していく関数である上に、定義の単純さから大きさの比較が容易なのだ。

第0歩 出発地点

\large{f(n)=n+1}
安心して欲しい。皆大好き(?)足し算だ。ただ足すだけだ。僕の黒歴史にもこんな奴がいるが、こいつは今回は関係無いのでもう出て来ない。

1を足しているだけでは全然大きくならないが、「数を大きくする」という意味ではここが原点であり全ての始まりであるとも言える。なのでこいつをレベル1と呼ぶことにする。レベルをわかりやすく右下に書いておこう。
\Large{f_{1}(n)=n+1}

第1歩 踏み出す

さて、1を足しているだけではさっぱりなのでこれを何重にも繰り返してみよう。
f_{1}(f_{1}(n))=n+1+1=n+2
f_{1}(f_{1}(f_{1}(n)))=n+1+1+1=n+3
f_{1}(f_{1}(f_{1}(f_{1}(n))))=n+1+1+1+1=n+4
fが一杯連なってチラチラしてきたので冪乗のように右上に数字を書いて表すことにしよう。
f_{1}^{2}(n)=n+2
f_{1}^{3}(n)=n+3
f_{1}^{4}(n)=n+4
m重に入れ子にすればこうなる。
f_{1}^{m}(n)=n+m
じゃあこれがmじゃなくて引数と同じnだったとしたら?
f_{1}^{n}(n)=n+n=2n
おお、掛算になった。これをレベル2の関数としよう。現れる文字が1つになったのだから引数は1つで十分だよね。
\Large{f_{2}(n)=f_{1}^{n}(n)=2n}
結論から言うとこのレベル2はレベル1より強い。レベル1の関数がいくつ束になってかかろうとレベル2がそれを上回り打ち破ってしまう。具体的にやってみよう。例えばレベル1を100個集める。
f_{1}^{100}(n)=n+100
f_{2}=n+n
この勝負はnに100を代入した瞬間に肩を並べそして100を超えた時点でレベル2がレベル1を超える。レベル1をどんなに重ねて繰り返してもその繰り返した分の引数を代入するだけでレベル2がそれを凌駕する。というわけでこれを式で表現しよう。
\large{f_{2}>f_{1}}

ちなみにこの様な手法を「対角化」と呼ぶ。こんな感じで対角線ぽいから。
{
\mathbf{\underline{f_{1}(1)=1+1}}\ ,\ f_{1}(2)=2+1\ ,\ f_{1}(3)=3+1\ ,\ f_{1}(4)=4+1\ ,\ \cdots \\
f_{1}^{2}(1)=1+2\ ,\ \mathbf{\underline{f_{1}^{2}(2)=2+2}}\ ,\ f_{1}^{2}(3)=3+2\ ,\ f_{1}^{2}(4)=4+2\ ,\ \cdots \\
f_{1}^{3}(1)=1+3\ ,\ f_{1}^{3}(2)=2+3\ ,\ \mathbf{\underline{f_{1}^{3}(3)=3+3}}\ ,\ f_{1}^{3}(4)=4+3\ ,\ \cdots \\
f_{1}^{4}(1)=1+4\ ,\ f_{1}^{4}(2)=2+4\ ,\ f_{1}^{4}(3)=3+4\ ,\ \mathbf{\underline{f_{1}^{4}(4)=4+4}}\ ,\ \cdots \\
\ \ \ \ \ \vdots\ \ \ \ \ \ \ \ \ \ \ \ \ \vdots\ \ \ \ \ \ \ 
\ \ \ \ \ \vdots\ \ \ \ \ \ \ \ \ \ \ \ \ \vdots\ \ \ \ \ \ \ \ 
\ \ \ \ \ \vdots\ \ \ \ \ \ \ \ \ \ \ \ \ \vdots\ \ \ \ \ \ \ \ 
\ \ \ \ \ \vdots\ \ \ \ \ \ \ \ \ \ \ \ \ \ \vdots \\
\Rightarrow \large{f_{2}(n) = n+n}
}

第2歩 繰り返す

レベル1の時と同様レベル2も繰り返してみる。
{
f_{2}(n)=2n \\
f_{2}^{2}(n)=2 \cdot 2n = 4n \\
f_{2}^{3}(n)=2 \cdot 2 \cdot 2n = 8n \\
f_{2}^{4}(n)=2 \cdot 2 \cdot 2 \cdot 2n = 16n \\
\ \ \ \ \ \vdots\ \ \ \ \ \ \ \ \ \ \ \ \ \vdots\\
f_{2}^{m}(n)=2^{m}n
}
「レベル1をn回繰り返したもの」がレベル2だったのだから、当然それを繰り返せばレベル3となる。
\large{f_{3}(n) = f_{2}^{n}(n) = 2^{n}n}
当然レベル3は先程と同様にしてレベル2よりも強いのです。
\large{f_{3} > f_{2}}

第m歩 終わらない旅路

レベル3は繰り返すと複雑になるので具体的な式を書くのはもう辞めます。正確な式の内容は割りとどうでもいいのです。
{
f_{3}(n) = f_{2}^{n}(n)\\
f_{4}(n) = f_{3}^{n}(n)\\
f_{5}(n) = f_{4}^{n}(n)\\
\ \ \ \ \ \vdots\ \ \ \ \ \ \ \ \ \ \ \ \ \vdots\\
f_{m}(n) = f_{m-1}^{n}(n)
}
そしてレベルの違いが強さの違いを表します。
{f_{1} < f_{2} < f_{3} < f_{4} < f_{5} < \cdots < f_{m-1} < f_{m} < \cdots}

\omega歩 限界を超えて

もう一度レベルアップの手順を思い出そう。
{
f_{1}(n) \rightarrow f_{1}^{2}(n) \rightarrow f_{1}^{3}(n) \rightarrow \cdots
\rightarrow f_{1}^{m}(n) \rightarrow f_{1}^{n}(n) = f_{2}(n) \\
f_{1}^{m} < f_{2}
}
「関数を繰り返した回数」と「最初の引数」という本来全く別の意味を持つ数に同じ数を代入することでレベルアップした関数を作ってきた。そしてレベルアップ後の関数はレベルアップ前の関数を何回繰り返したものより強かった。じゃあレベルnの関数作ればめっちゃ強いんじゃね? 実際にやってみよう。これも先述の「対角化」だ。この強そうな関数をレベルが付けられないのでとりあえずFとしておく。
{
f_{1}(n) \rightarrow f_{2}(n) \rightarrow f_{3}(n) \rightarrow \cdots
\rightarrow f_{m}(n) \rightarrow f_{n}(n) = F(n) \\
f_{m} < F
}
 じゃあFのレベルを考えてみよう。レベル1よりは当然強い、レベル2よりも強いしレベル3よりも……。というかぶっちゃけどんなレベル○○よりも強い。そこでこれをレベルωと呼ぶことにする。
\Large{f_{\omega}(n)=f_{n}(n)}
 「ωってなんだよ厨二病かよ」と思うかもしれないがωもれっきとした数の一種である。「超限順序数」と呼ばれるなんともかっこいい名前の代物なのだが詳しくやると本が一冊必要な話になるのでざっくり解説しよう。
 まず、「数とは何か」を考える。分数とか無理数とかは考えず整数のみについて考えると数とは「1,2,3……」というように順番に並んで続いているものだ。「nの次の数」と言えばそれは「n+1」でしかあり得ず他には無い。そんな物を「数」と呼ぶことにしよう。その「数」という括りの中で1から始まる物を「自然数」と呼ぶ。ここは僕達の普段イメージしている自然数と同じものだ。そしてωはそのあらゆる"自然数"よりも大きい"数"なのだ。当然"数"であるからにはωも続いている「ω,ω+1,ω+2,……」と続く。ただし、これは僕達が普段イメージする数とは少し性質が異なる。例えば「ωの前の数(ω-1)」は存在しない。それは自然数の中で「最大の自然数」なのだが、それは存在しないからだ。
 というわけで図にするとこんな感じになる。一行の中では右に行けば行くほど大きく、下の行は上の行のどの数よりさらに大きい。
{
\underline{1},2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, \cdots \\
\underline{\omega}, \omega + 1, \omega + 2, \omega + 3, \omega + 4, \omega + 5, \omega + 6, \cdots \\
\omega + \omega = \underline{\omega \cdot 2},\  \omega \cdot 2 + 1, \omega \cdot 2 + 2, \omega \cdot 2 + 3, \cdots \\
\omega \cdot 2 + \omega = \underline{\omega \cdot 3},\  \omega \cdot 3 + 1, \omega \cdot 3 + 2, \omega \cdot 3 + 3, \cdots \\
\ \ \vdots \\
\omega \cdot \omega = \omega^{2}, \cdots \\
\ \ \vdots \\
\omega^{3}, \cdots \\
\ \ \vdots \\
\omega^{4}, \cdots \\
\ \ \vdots \\
\omega^{\omega}, \cdots \\
\ \ \vdots \\
\omega^{\omega^{\omega}}, \cdots \\
\ \ \vdots \\
}
要するにωはどんな自然数より大きく、更にそれより大きい数があるということだ。
f_{\omega} > f_{m}(※m自然数)
f_{\omega + 1}(n) = f_{\omega}^{n}(n)
{
f_{\omega} \rightarrow f_{\omega + 2} \rightarrow f_{\omega + 3} \rightarrow \cdots 
\rightarrow f_{\omega \cdot 2} \rightarrow \cdots \rightarrow f_{\omega \cdot 3} 
\rightarrow \cdots \rightarrow f_{\omega^{2}} \rightarrow \cdots 
}
{
f_{\omega} < f_{\omega + 2} < f_{\omega + 3} < \cdots < f_{\omega \cdot 2}
 < \cdots < f_{\omega \cdot 3} < \cdots < f_{\omega^{2}} < \cdots 
}
とまぁこんな具合に急激に増加していくから急増加関数と呼ばれるわけだ。ωとか書いてあると目が回りそうになるかもしれないが何の事はない計算するときはωをnに置き換えるだけで良い。軽く実例を上げて計算してみよう。f_{\omega^{\omega}}(n)n=2を代入したものを計算してみよう。
{
f_{\omega^{\omega}}(2) = f_{2^{2}}(2) = f_{4}(2) = f_{3}^{2}(2) = f_{3}(f_{3}(2))\\
\ = f_{3}(2^{2} \cdot 2) = f_{3}(8) = 2^{8} \cdot 8 = 2048
}
「なんだ大したこと無い」と思うかもしれないがそしたら次は3を代入してみると良い。その時点で既に10進表記では対処しきれない恐ろしい数になる。

全ての果てに

急増加関数が如何に化け物じみた関数かお分かり頂けだろうか。化け物に化け物を重ねてそれを対角化することで更に強い化け物を作り続ける事が出来るとても恐ろしい関数なのだ。で、こいつはただ恐ろしいだけじゃなく「繰り返す」「対角化する」という手順自体を「レベル」という大きさを比較できる形で示してくれている。色々な関数をこの急増加関数と比較し「どの程度のレベルか」を特定すれば複雑な関数同士の比較も明確になる便利なものさしの役割を果たしてくれるわけだ。具体的にどうやって比較していくのか。ちょっと自信無いんだけどとりあえず続編でチャレンジしてみようと思います。アッカーマン関数辺りから戦ってみようかな。では、そんな感じで。