この記事はtraP Advent Calendar 2023 14日目の記事です。

みなさん。大きい数と聞いて何を思い浮かべるでしょうか？
億？兆？京？無量大数？不可説不可説転？
Googleの名前の由来とも言われるグーゴル（googol）=$10^{100}$やグーゴルプレックス（googleplex）=$10^{10^{100}}$。
数学の証明に使用されたことのある最大の数である、グラハム数などを知っている人もいるかもしれません。

今回は、とにかく大きい数を作る芸術のような数学、巨大数という分野についての話です。
（巨大数wikiを大いに参考にさせて頂いております。）

注意:ここから話す"数"には制限をかけます。
具体的には、0を含む自然数（非負整数）とします。
以降、数、自然数と言ったら非負整数を指します。
つまり、小数や負の数、ましてや無限大という数は存在しません。（ややこしいのですが、別の数の定義として、自然数を含み、無限大のような数も許した順序数という数が出てきますが、あくまで別物と考えてください。）

何も考えずデカい数を作ってみる

まず、大きい数を普通に作ってみましょう。9をたくさん書けばいいのです。

9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999

これは、このように略記することができます。

$9が100個$

また、このように近似できます。

$9が100個\approx 10^{100}$

ここで大きさに重要なのは、底（10にあたる部分）ではなく指数（100にあたる部分）です。
底を10倍することと、指数に1を足すことが等価なことからすぐにわかります。
なので、このデカイ数をそのまま指数にしてしまいましょう。

$10^{10^{100}}$

そして、これをたくさん書けばいいですね。

$10^{10^{10^{10^{10^{10^{10^{10^{10^{10}}}}}}}}}$

そして、このように略記することができます。

$10を指数に10個重ねたもの$

もうなんとなく分かりましたね。
この個数を、そのままこの数に置き換えてしまえばよいのです。
ここでこのような略記を導入します。

• $a\uparrow b=a^b$
• $a\uparrow \uparrow b=a\uparrow a\uparrow \cdots \uparrow a(aがb個)$

もちろんこの矢印は一番右から計算していきます。
そうすると、置き換えたものはこう書けます。

$10\uparrow \uparrow 10\uparrow \uparrow 10$

もうなぜ上のような書き方を定義したのかわかるはずです。
たくさん書いて、略記して、たくさん書いて、略記して、を繰り返します。
矢印を増やして定義していき、その矢印の個数をべき乗の形で書くイメージです。
具体的には以下のように定義します。

• $a{\uparrow }^{1}b=a^b(a{\uparrow }^{0}b=a\times bやa{\uparrow }^{-1}b=a+bとしてもよいです。)$
• $a{\uparrow }^{n+1}b=a{\uparrow }^{n}a{\uparrow }^n\cdots {\uparrow }^{n}a(aがb個)$

これも右から計算していきます。
もう感のいい人は気づいたかも知れませんね。
そう、この矢印の指数に大きい数を入れてしまいましょう。具体的には以下のように定義します。

• $G(n)=3{\uparrow }^{n}3$
• $G^m(n)=G(G(\cdots G(n)\cdots ))(関数Gをm回合成する)$

そしてついにたどり着きました。
グラハム数は$G^{64}(4)$と定義されます。
そして気付くはずです。
グラハム数はまだ大きい数とは言えないことに。
（なぜ3なのかは、2にしてみて実際に計算すればなんとなくわかります。）
ちなみにこの上矢印の書き方は矢印表記や上矢印表記と呼ばれ、巨大数ではまだLv.1の小ささです。
小さいです。

大きい数が作れる本質を見極め、もっと大きくする

さて今までのことを整理して、この方法で大きい数が作れる本質は何かを考えてみましょう。
やったことは、①略記、②たくさん書くです。
ここで$G(n)$の例を考えると、②は関数の合成として見ることができます。
そして①は②での合成の回数を変数として、新たな関数を定義すること、として見ることができます。
これを踏まえると以下のような関数を定義できます。

• $f_0(n)=n+1$
• $f_{m+1}(n)=f_m^n(n)=f_m(f_m(\cdots f_m(n)\cdots ))(n回合成)$

この関数を矢印表記で近似してみると、

$f_1(n)=n+1+\cdots +1=2n$
$f_2(n)=2\times \cdots \times 2\times n=2^n\times n\approx 2^n=2\uparrow n$
$f_3(n)\approx 2\uparrow \cdots \uparrow 2\uparrow n\approx 2{\uparrow }^{2}n$
$f_{m+1}(n)\approx 2{\uparrow }^{m}n$

そして、グラハム数の定義に使った関数は、$G(n)=3{\uparrow }^{n}3\approx f_{n+1}(3)$と近似できます。
実は、$G(n)$は任意の自然数mについて$f_m(n)$よりも強いので、グラハム数は大体の矢印表記で書かれた数より大きいです。
この"関数の強さ"についてもう少し詳しく解説、定義します。
この後に説明する、関数を強くする方法"対角化"は、巨大数でもかなり重要な概念、考え方です。

強い関数の定義を見れば、明らかに$G(n)\approx f_n(n)$は任意の自然数$m$について$f_m(n)$より強いことがわかります。（この、定数を変数化する、決まっているものを変数にしてより強くすることを対角化と言ったり言わなかったりします。）
もう少しわかりやすく言うと、$f_n(n)$と$f_{10000000}(n)$では、10000000より大きい数を代入すれば$f_n(n)$の方が大きい数を作れるということです。（この大きさの違いは、$n^m$と$n^n$のように、圧倒的な違いを生み出すことを確認してください。）
もう慣れてきましたね。
この$f_n(n)$という関数を新たに$g_0(n)$と置き、同じように任意の添字について定義をすればより強い関数を作れます。
そして$h_m(n),i_m(n),j_m(n)$と続けていく...？
違いますよね。
もちろん数字で置いて定義します。
イメージとしては$f_m=f_{0,m}{g}_m=f_{1,m}$という風に定義します。

• $f_{0,0}(n)=n+1$
• $f_{a,b+1}(n)=f_{a,b}^n(n)$
• $f_{a+1,0}(n)=f_{a,n}(n)$

そして$f_{a,b}(n)$より強い関数として$f_{n,0}(n)$という関数があって、それを$f_{1,0,0}(n)$と置いて、より強い関数$f_{n,0,0}(n)$を$f_{1,0,0,0}(n)$と置いて...そろそろ分かってきたと思います。
添字の個数を変数にした関数はより強い関数になります。
しかし、このまま強くし続けても表記が汚くなってしまいそうです。
ここで、この添字に順序数という新しい数（自然数ではない）を使います。
この順序数という概念を使えば、思ってるよりもずっと大きな数を簡単に、しかもわかりやすく定義できます。

とりあえず、関数の添字（数列）で、関数の定義として使っている性質を列挙します。

1. 最も小さい添字($\dots ,0,0$)が存在する　(関数の実体を定義しているのは$f_0(n)=n+1$のみ)
2. ある添字について、必ず次の添字(添字の一番右の数を$+1$したもの)が存在する　(これで関数の合成をしている)(使う添字より小さい添字に対して存在すれば実用上十分である)
3. ある添字が何らかの添字の次にならない(添字の一番右の数が0である)場合、大きい数$n$を使って、より小さい添字であってかつそれなりに大きい添字を作れる($2,0,0$から$1,n,0$)　(これで関数の対角化をしている)
4. 1つ前の添字にする、または上の操作によって得られる添字にすることによって、添字を小さくし続けるという操作が有限で終わる(結局は$f_0$をとてつもなく繰り返しているだけなので、いつか$f_0$にたどり着かなければいけない)

あと副産物として、関数の強さの比較が添字の比較で決まります。
この上の4つを満たすものが、数列ではなく普通の数として定義できればいいですよね？
実はできるんです。
順序数は自然数の拡張として定義されます。
よって最も小さい添字は0です。（性質1はクリア）
ここで、全ての自然数より大きい数を考えます。
これを$\omega$と置きます。
つまり以下が成り立ちます。

任意の自然数$m$に対して$\omega >m$

何かすごく関数の強さでやった対角化っぽいですよね？
実はこれは添字$1,0$に対応します。
$\omega$は前の順序数がなく、より小さいけどその中では大きい順序数（この場合そのままn）を作れるので性質3を満たし、nは有限であることから性質4も満たす。
また、$\omega +1$のような順序数も考えられ、これは添字$1,1$に対応することもすぐにわかります。
もちろん性質は全て満たしたままです。

また、$\omega$は数列$(0,1,2,3,\cdots )$の極限のようにも見えますね。
よって以下のように用語を定義します。
ある広義単調増加順序数列（常により大きくなり続ける順序数の列）の極限（この数列に出てくるどの順序数よりも大きい順序数）であって最も小さいもの（前の順序数が存在しないもの）を極限順序数。
極限順序数を定義する広義単調増加順序数列を基本列とする。
この時、$\omega$の基本列として$(0,2,4,6,\cdots )$も条件を満たしてしまいますが、今回は$(0,1,2,3,\cdots )$の1つに絞ります。
そして、性質3を使う順序数は定義より極限順序数に限り、極限順序数にはそれを定義する基本列が存在するので、基本列のn番目の順序数(0番目が最初)と定義する。
これを、極限順序数$\alpha$に対し$\alpha [n]$とする。
以上を踏まえ、関数を以下のように定義する。

• $f_0(n)=n+1$
• $f_{\alpha +1}(n)=f_{\alpha }^n(n)$
• $f_{\alpha }(n)=f_{\alpha [n]}(n)(\alpha が極限順序数の時)$

あとは基本列から極限順序数を定義していき、より大きい順序数を作っていくだけです。
（実際は足し算や掛け算の順番に決まりがあったり、掛け算には$\times$の記号は使わなかったりするのですが、特に気にしないで計算ができればいいです。今回は、より小さい順序数を右側に置くようにしています。）
大体のイメージは以下のようになります。

$\omega +0(=\omega ),\omega +1,\omega +2,\cdots \to \omega +\omega =\omega \times 2$
$\omega \times 0(=0),\omega \times 1(=\omega ),\omega \times 2,\cdots \to \omega \times \omega ={\omega }^2$
${\omega }^0(=1),{\omega }^1(=\omega ),{\omega }^2,{\omega }^3,\cdots \to {\omega }^{\omega }$
$1,{\omega }^1,{\omega }^{{\omega }^1},\cdots \to {ϵ}_0$

もう少し正確に定義すると、以下のように$\alpha [n]$を定義します。(ワイナー階層という名前がついてます。)

1. $\omega [n]=n$
2. ${\omega }^{\alpha +1}[n]={\omega }^{\alpha }\times n$
3. ${\omega }^{\alpha }[n]={\omega }^{\alpha [n]}(\alpha が極限順序数の時)$
4. $(\beta +{\omega }^{\alpha })[n]=\beta +{\omega }^{\alpha }[n](\beta は{\omega }^{\alpha }以上の順序数とする)$
5. ${ϵ}_0[0]=1$
6. ${ϵ}_0[n+1]={\omega }^{{ϵ}_0[n]}$

実際に具体的に計算してみましょう。

${\omega }^{\omega }[n]={\omega }^{\omega [n]}={\omega }^n$
${\omega }^3[n]={\omega }^{2+1}[n]={\omega }^2\times n$
${\omega }^2\times 3[n]=({\omega }^2\times 2+{\omega }^2)[n]={\omega }^2\times 2+{\omega }^2[n]={\omega }^2\times 2+{\omega }^{1+1}[n]={\omega }^2\times 2+\omega \times n$
$({\omega }^2\times 2+\omega \times 3)[n]=({\omega }^2\times 2+\omega \times 2+\omega )[n]={\omega }^2\times 2+\omega \times 2+\omega [n]={\omega }^2\times 2+\omega \times 2+n$

$\alpha [n]$もまた極限順序数になる場合もあります。
これを踏まえて数列の添字と順序数を対応させてみます。

$f_{1,0}(n)=f_n(n)=f_{\omega [n]}(n)=f_{\omega }(n)$
$f_{1,1}(n)=f_{1,0}^n(n)=f_{\omega }^n(n)=f_{\omega +1}(n)$
$f_{1,m}(n)=f_{\omega +m}(n)$
$f_{2,0}(n)=f_{1,n}(n)=f_{\omega +n}(n)=f_{\omega +\omega [n]}(n)=f_{(\omega +\omega )[n]}(n)=f_{\omega \times 2[n]}(n)=f_{\omega \times 2}(n)$
$f_{m,0}(n)=f_{\omega \times m}(n)$
$f_{1,0,0}(n)=f_{0,n,0}(n)=f_{\omega \times n}(n)=f_{{\omega }^2[n]}(n)=f_{{\omega }^2}(n)$
$f_{1,0,\cdots ,0(0がm個)}(n)=f_{{\omega }^m}(n)$

そして、${\omega }^n={\omega }^{\omega [n]}={\omega }^{\omega }[n]$より、添字の個数を変数化した関数は$f_{{\omega }^{\omega }}(n)$と書けます。

実は、$f_{{ϵ}_0}(n)$であらわされる関数はとてつもなく大きく、今後紹介するほぼ全ての関数が${ϵ}_0$より小さい順序数を使って近似できます。
よってこの順序数を使った関数$f_{\alpha }(n)$は急増加関数と呼ばれ、様々な関数を近似し、その強さを比べる指標としてよく使われます。（実際は${ϵ}_0$では足りず、もっと大きな順序数を定義してより強い関数まで近似できるようになっていますが、より定義が複雑で難しくなっていくのでここでは扱いません。）

イカれた巨大数たちを紹介するぜ！

ここでは別のアプローチによる関数や表記を、その関数や表記の大きさを近似する急増加関数の順序数と一緒に、その順序数の順番に紹介します。
関数名を押すと巨大数Wikiに飛ぶので、近似の詳細等が知りたい場合は是非訪れてみてください。

レベル $\omega$:アッカーマン関数

競プロを嗜む人は、Union-Findの計算量として、この関数の逆関数を聞いたことがあるでしょう。
実は、この関数の定義は3種類もあります。
どれも強さは同じなのですが、今回は一番有名なロビンソンによる定義を使用します。
とりあえず定義は以下のようになります。

• $A(0,y)=y+1$
• $A(x+1,0)=A(x,1)$
• $A(x+1,y+1)=A(x,A(x+1,y))$

この関数を矢印表記で表すとこのようになります。

$A(0,y)=2{\uparrow }^{-2}(y+3)-3=y+1$
$A(1,y)=2{\uparrow }^{-1}(y+3)-3=y+2$
$A(2,y)=2{\uparrow }^0(y+3)-3=2\times y+3$
$A(3,y)=2{\uparrow }^1(y+3)-3=2^{y+3}-3$
$A(x,y)=2{\uparrow }^{x-2}(y+3)-3$

法則性を分かりやすくするために、ここでは矢印表記を以下のように拡張しています。（このようにしても矢印表記の法則が成り立つことを確認してください。）
$x{\uparrow }^{-2}y=y+1x{\uparrow }^{-1}y=x+yx{\uparrow }^{0}y=x\times y$

そして一変数にした$A(n)=A(n,n)$という関数は$f_{\omega }(n)$で近似できることがわかります。

レベル ${\omega }^2$:チェーン表記

定義は4つのルールで決まります。

• $a\to b\to c=a{\uparrow }^{b}c$ ($a\to b=a^b$としてもよい)
• $a\to \cdots \to b\to 1=a\to \cdots \to b$
• $a\to \cdots \to b\to 1\to c=a\to \cdots \to b$ (上と合わせて、最後から2つまでに1があったら短くできる、と解釈できる。)
• $a\to \cdots \to b\to (c+1)\to (d+1)=a\to \cdots \to b\to (a\to \cdots \to b\to c\to (d+1))\to d$

この表記は意外と強く、$3\to 3\to 64\to 2<$グラハム数$<3\to 3\to 65\to 2$が成り立ち、$3\to 3\to 3\to 3$でグラハム数を圧倒的に超えます。

そして、$n\to n\to \cdots \to n$($n$個の$n$)$\approx f_{{\omega }^2}(n)$が成り立ちます。

レベル ${\omega }^{\omega }$:多変数アッカーマン関数

急増加関数で添字の数列の個数を増やしたような拡張を、アッカーマン関数に対して適用したものです。
定義は以下のようになります。

• $A(0,\cdots ,0,y)=y+1$
• $A(a,\cdots ,x+1,0)=A(a,\cdots ,x,1)$
• $A(a,\cdots ,x+1,y+1)=A(a,\cdots ,x,A(a,\cdots ,x+1,y))$
• $A(a,\cdots ,b+1,0,0,\cdots ,0,y)=A(a,\cdots ,b,y,0,\cdots ,0,y)$

イメージとしては$A(a,\cdots ,b,x,y)$を$A_{a,\cdots ,b,x}^{\prime }(y)$とすると、以下のような形になるので分かりやすいかもしれません。

• $A_{0,\cdots ,0}^{\prime }(y)=y+1$
• $A_{\cdots ,x+1}^{\prime }(0)=A_{\cdots ,x}^{\prime }(1)$
• $A_{\cdots ,x+1}^{\prime }(y)=A_{\cdots ,x}^{\prime y}(0)$
• $A_{\cdots ,b+1,0,\cdots ,0}^{\prime }(y)=A_{\cdots ,b,y,\cdots ,0}^{\prime }(y)$

自分は、急増加関数の強さは合成回数の変数化にあって、合成元の関数に元の変数を代入する必要はなく、1を入れるだけで十分である。と理解しています。（実際に急増加関数による近似は一致する。）

そして、$A(1,\cdots ,1)$($n$個の1)$\approx f_{{\omega }^{\omega }}(n)$となります。

レベル ${\omega }^{\omega }$:配列表記(BEAF)

一見チェーン表記と似ているが、そこから生まれる数は大きさの格が違う。
以下定義です。

1. $\{a\}=a$
2. $\{a,b\}=a^b$
3. $\{a,\cdots ,b,1\}=\{a,\cdots ,b\}$
4. $\{a,1,\cdots \}=a$
5. $\{a,b+1,1,\cdots ,1,c+1,\cdots \}=\{a,a,a,\cdots ,\{a,b,1,\cdots ,1,c+1,\cdots \},c,\cdots \}$
6. $\{a,b+1,c+1,\cdots \}=\{a,\{a,b,c+1,\cdots \},c,\cdots \}$

自分はこの定義を以下のように解釈しています。

1. 基本の定義
2. 最終出力のための定義
3. 最終出力のために配列を短くするする定義
4. 5,6を途中で止めるための定義
5. 多変数アッカーマン関数の4番目と同じ目的
6. 同上

イメージとしては以下のように数が増えていきます。(大きい数になったものを$★$で表します。)

$\{a,b,c,d,e,\cdots \}$
$\{a,★,c-1,d,e,\cdots \}$ (6)
$\{a,★,1,d,e,\cdots \}$ (6の繰り返し)
$\{a,a,★,d-1,e,\cdots \}$ (5)
$\{a,★,★-1,d-1,e,\cdots \}$ (6)
$\{a,★,1,d-1,e,\cdots \}$ (6の繰り返し)
$\{a,a,★,d-2,e,\cdots \}$ (5)
$\{a,★,1,1,e,\cdots \}$ (以上の繰り返し)
$\{a,a,a,★,e-1,\cdots \}$ (5)
$\{a,★,1,\cdots 1,2\}$ (以上の繰り返し)
$\{a,a,a,\cdots ★,1\}$ (そして最後の数が1になる)
$\{a,a,a,\cdots ★\}$ (配列の長さが1縮む)
$\{a,★1\}$ (以上の繰り返し)
$\{a,★\}$ (配列の長さが2になる)
$a^{★}$ (最終結果)

そして、$\{n,\cdots ,n\}$($n$個の$n$)$\approx f_{{\omega }^{\omega }}(n)$となります。
（この配列表記は様々な方法でさらに拡張されて、より強い表記がたくさんあります。）

レベル ${ϵ}_0$:ヒドラ関数

少し違ったアプローチによる関数です。
ヒドラとは、ギリシャ神話に出てくる複数の首を持った蛇の怪物の名前です。
以下のような文字列と操作を考えます。

正しく括弧の対応が取れる、(,)のみからなる文字列をヒドラとする。((と)の数が同じものと考えればいいです。)
ヒドラ中に出てくる空の括弧()を頭とする。
ある頭に対して、頭を直接囲む括弧がもし存在するなら、その括弧と内側を首と呼ぶ。
あるヒドラと数$k$に対し、頭を切る($k$)という操作を以下のように定義する。

1. 頭を一つ選び、消す
2. 首があれば、その首を$k$個複製する

また、頭を切ってヒドラが無くなった時、ヒドラを倒したと呼ぶ。

例えば、(),(()),(()()),(()(()(())((()))))はヒドラです。
(,)(,(()はヒドラではありません。
ヒドラの頭を赤色に、首を太字にするとこのようになります。
(()()),(()(()()(())))
頭を切る操作の例を示します。
例1：$k=2$の時、(()(()()))$\to$(()(()))$\to$(()(())(())(()))
例2：$k=12$の時、()$\to$（この時、ヒドラは倒されています。）

そして、あるヒドラに対して以下のような操作の繰り返しをヒドラゲームと呼びます。

1. ターン数を$T=1$とする
2. 以降以下の操作を繰り返す
   1. 頭を一つ選び、頭を切る($T$)
   2. ヒドラが倒されたら止める
   3. ターン数$T$を一つ増やす

このヒドラゲームは、全てのヒドラに対して、どのように頭を選んだとしても、必ずゲームが終わることが証明されています。

そしてヒドラ関数$Hydra(n)$は以下のようになります。
ヒドラ((...()...))(n個の括弧)に対してヒドラゲームを行ったときにかかるターン数の最大値

$Hydra(1)$,$Hydra(2)$,$Hydra(3)$を求めてみます。（最大になる選び方のみ示します。）

$Hydra(1)=1$
T=1 : ()
倒した

$Hydra(2)=3$
T=1 : (())
T=2 : ()()
T=3 : ()
倒した

$Hydra(3)=37$
T=1 : ((()))
T=2 : (()())
T=3 : (())(())(())
T=4 : (())(())()()()()
T=5 : (())(())()()()
T=6 : (())(())()()
T=7 : (())(())()
T=8 : (())(())
T=9 : (())()()()()()()()()()
T=10 : (())()()()()()()()()
T=11 : (())()()()()()()()
T=12 : (())()()()()()()
T=13 : (())()()()()()
T=14 : (())()()()()
T=15 : (())()()()
T=16 : (())()()
T=17 : (())()
T=18 : (())
T=19 : ()()()()()()()()()()()()()()()()()()()
T=20 : ()()()()()()()()()()()()()()()()()()
T=21 : ()()()()()()()()()()()()()()()()()
T=22 : ()()()()()()()()()()()()()()()()
T=23 : ()()()()()()()()()()()()()()()
T=24 : ()()()()()()()()()()()()()()
T=25 : ()()()()()()()()()()()()()
T=26 : ()()()()()()()()()()()()
T=27 : ()()()()()()()()()()()
T=28 : ()()()()()()()()()()
T=29 : ()()()()()()()()()
T=30 : ()()()()()()()()
T=31 : ()()()()()()()
T=32 : ()()()()()()
T=33 : ()()()()()
T=34 : ()()()()
T=35 : ()()()
T=36 : ()()
T=37 : ()
倒した

実は、$Hydra(4)$はグラハム数を超える値になり、$Hydra(5)>f_{{\omega }^{\omega \times 2+4}}(5)$が成り立ちます。
そして$Hydra(n)\approx f_{{ϵ}_0}(n)$です。
このヒドラゲームを少し改変すると、後に紹介するTREE関数より強くなります。

レベル ${ϵ}_0$:原始数列システム

ついにプログラミング言語で定義された数が出てきます。
実際には、原始数列数と名付けられた数を出力する疑似BASICプログラムが公開され、そのアルゴリズムを関数として見た時の強さが${ϵ}_0$です。
以下その疑似プログラムを示します。

main.basdim A(∞):B=9
for C=0 to 9
  for D=0 to B
    A(D)=D
  next
  for E=B to 0 step -1
    B=B*B
    for F=0 to E
      if A(E-F)<A(E) or A(E)=0 then G=F:F=E
    next
    for H=1 to B*G
      A(E)=A(E-G):E=E+1
    next
  next
next
print B

自分はC++erなので、C++で書いたものも置いておきます。

main.cpp#include <iostream>
int A[∞], B = 9, C, D, E, F, G, H;
int main(void) {
  for (C = 0; C <= 9; C++) {
    for (D = 0; D <= B; D++) A[D] = D;
    for (E = B; E >= 0; E--) {
      B*=B;
      for (F = 0; F <= E; F++) {
        if (A[E - F] < A[E] || A[E] == 0) {
          G = F;
          break;
        }
      }
      for (H = 1; H <= B * G; H++) {
        A[E] = A[E - G];
        E++;
      }
    }
  }
  std::cout << B;
  return 0;
}

原始数列システムを関数$P(n)$とします。
このとき、プログラムで出力される値は$P^{10}(9)$です。
$P(n)$の数学的な定義は以下のようになります。

数列$S=(S_0,S_1\cdots ,S_k)$と数$n$に対し、整数$S[n]$を以下のように定める

• $S$が空の数列の時、$S[n]=()[n]=n$
• $S$が空の数列でない時
  $S$の悪い部分$b$(数列で$S$の一部)を以下のように定める
  • $i<k$かつ$S_i<S_k$を満たす$i$が存在するならば、$b=(S_i,\cdots ,S_{k-1})$
  • 存在しないとき、$b=()$
    そして$S[n]=(S_0,S_1,\cdots ,S_{k-1},b,\cdots ,b)[n^2]$（$n^2$個の$b$）とする

そして、$P(n)=(0,1,\cdots ,n)[n]$とする

例えば、$(2,0,5,3)[2]=(2,0,5,0,5,0,5,0,5,0,5)[4],(5,4,3,2,1)[10]=(5,4,3,2)[100]$となります。

$P(n)$をC++で定義すると以下のようになります。

primitive_sequence_function.cppint P(int n) {
  int A[∞], B = n, C, D, E, F, G, H;
  for (D = 0; D <= B; D++) A[D] = D;
  for (E = B; E >= 0; E--) {
    B*=B;
    for (F = 0; F <= E; F++) {
      if (A[E - F] < A[E] || A[E] == 0) {
        G = F;
        break;
      }
    }
    for (H = 1; H <= B * G; H++) {
      A[E] = A[E - G];
      E++;
    }
  }
  return B;
}

そして$P(n)\approx f_{{ϵ}_0}(n)$となり、原始数列数$=P^{10}(9)\approx f_{{ϵ}_0}^{10}(9)\approx f_{{ϵ}_0+1}(10)$です。

この表記を改良したバシク行列システムは、対応する順序数がいまだに知られていないほど超強力な関数になります。

レベル $\vartheta ({\Omega }^{\omega }\omega )$:TREE関数

いきなり変な記号の羅列が出てきましたが、これは${ϵ}_0$よりクソデカいよくわからん順序数を使って、難しい集合論を使って定義された関数$\vartheta$に入れていい感じに基本列を作れる順序数にしたものと思ってくれればいいです。

この関数にはグラフ理論が使われており、グラフ理論をよく知らない、わからない人は、この動画でも見てなんとなく理解してください。
†グラフ理論何もわからん†の人も見ることをお勧めします。
以下定義です。

1. $T_i$の頂点数は$i$以下である
2. $i<j$を満たす$i,j$全てについて、$T_i$が$T_j$にinf保存かつラベル保存埋め込み可能でない

を満たすような根付きn-ラベル付き木の列($T_0,T_1,\cdots$)であって、最も長い列の長さを$TREE[n]$とする

これは本当に頭がおかしくなるくらいに増加して、$TREE[1]=1,TREE[2]=3,TREE[3]>$(今まで紹介した関数で現実的に書ける数)になります。

レベル 計算不能Lv.1:ビジービーバー関数

ついにレベルが計算不能になりましたが、これ以降に紹介する関数は文字通り計算不可能な関数たちです。
この関数の発想は、今まで出てきた関数が有限の文字数でプログラミングできるなら、C++で$n$文字以下で書かれたプログラムで出力できる最大の数、みたいな感じでプログラミング言語そのものを対角化してしまえばいいじゃない、という感じです。

まず計算可能とは何かを説明しますと、有限の文字数でちゃんとプログラミングできる、と考えてくれれば大体大丈夫です。（つまり、ビジービーバー関数は有限の文字数でちゃんとプログラミングできません。）
多少情報科学を知っている人用に向けて説明すると、有限状態チューリングマシンで有限のステップで停止して答えを出力可能、と同値です。

ビジービーバー関数の定義は、$\Sigma (n)=$(全ての$n$-状態 2-記号チューリングマシンについて、空のテープから始めて停止するまでにテープに書かれた1の数の最大値)です。

この関数がなぜ計算不可能で、今まで紹介したどの関数より強いのかの感覚を説明します。

プログラムには無限ループが存在します。
なので、どのようなプログラムでも、n文字以内で書かれたプログラム全てを有限の時間で列挙することはできても、実際にそのプログラムを実行したときにどんな値が出るかを有限の時間で確認できません。（無限ループするかどうかを有限の時間で判断できないという意味です。）
そして、チューリングマシンというのは、パソコンと同じ性能を持つ、簡単な数学的モデルと思ってください。
同じ性能であるとは、パソコンにできることとチューリングマシンにできることが同じ、互いにシミュレーション可能、という意味です。
つまりプログラムに無限ループが存在するように、チューリングマシンにも無限ループが存在して、その出力を有限の時間で確認できません。
なので$\Sigma (n)$は有限の文字数でちゃんとプログラミングできない。
つまり計算不可能です。

また、チューリングマシンには状態数というものがあり、これはプログラミング言語の文字数に相当すると思ってください。
なので$n$(=状態数)を十分に大きくすれば、有限の文字数で書かれたプログラムをシミュレーションできるので、今まで紹介したどの関数もシミュレーションできる。
つまりどの関数よりも強いことになります。

さてこの関数の強さはパソコンを使って有限の時間で計算できるありとあらゆる関数より強いことがわかりました。
しかし計算不能"Lv.1"です。
ではLv.2に行きましょう。（このLv.nは、あくまで強さの比較をわかりやすくるためのもので、一般的に計算不可能関数を比較する基準ではありません。）

レベル 計算不能Lv.2:クサイ関数

さて、今までの議論を理解していれば、Lv.2なんて存在しなさそうです。
なぜなら、パソコンはなんでもできるからです。
しかし、唯一言及した"出来ないこと"がありましたね。
それは"無限ループするかどうかを有限の時間で判断すること"でしたね？
しかし、あるプログラムに対して、無限ループするかしないかは決まっています。
なので、それをまるで神託のように教えてくれるプログラム、神託機械を考えます。
実際には、プログラム$P$に対して、$P$が無限ループするなら1を、しないなら0を返す関数のように定義します。
なぜLv.2なのかの詳しい説明は、クサイ関数の定義の後します。

クサイ関数には、チューリングマシンとは別の簡単な数学的モデルである、SKIコンビネータ計算が使われています。
これは異常なほど簡単なので、定義を紹介します。

コンビネータと呼ばれる3つの記号$S,K,I$に対し、ベータ簡約を以下のように定義する（(,)は式のまとまりを示すためのもので、式の文字数には数えない。後ろに書いてある式は、よく使う関数のような書き方をして可読性を高めたもの）

• Ix=x ($I(x)$=$x$)
• Kxy=x ($K(x,y)$=$x$)
• Sxyz=xz(yz) ($S(x,y,z)$=$x(z,y(z))$)

一番左のコンビネータを使ってベータ簡約することを出来なくなるまで繰り返して、最終的に得られる式を出力結果、出力結果に含まれる文字数を出力サイズとする（ベータ簡約が終わらない場合、出力結果も出力サイズも存在しない）

以下SKIコンビネータ計算の例を置いておきます。

Kあいう=$K(あ,い)う$=$あう$=あう

Sabc=$S(a,b,c)$=$a(c,b(c))$=ac(bc)

S(かっこ)い(いね)=$S((かっこ),い,(いね))$=$(かっこ)((いね),い((いね)))$=
(かっこ)(いね)い(いね)=
かっこ(いね)い(いね)

SKS(KIS)$=S(K,S,(KIS))=K((KIS),S((KIS)))=$
K(KIS)(S(KIS))$=K((KIS),(S(KIS)))=(KIS)=$
(KIS)$=$
KIS$=K(I,S)=I=$
I

このSKIコンビネータ計算は、こんな見た目をしていますが、チューリングマシンをシミュレーションできます。
なので同じように無限ループするSKIコンビネータ計算が存在します。

SII(SII)=I(SII)(I(SII))=
SII(I(SII))=I(I(SII))(I(I(SII)))=I(SII)(I(I(SII)))=
SII(I(I(SII)))...

そしてこのSKIコンビネータ計算に、神託機械に相当する神託コンビネータΩを追加します。

• Ωxyz=xの最終的な出力結果が存在してIであるならy、そうでないならz

計算例は以下のようになります。

Ω(KIS)SK=S (KIS=I)
Ω(SII(SII))SI=I (SII(SII)は無限ループする)
Ω(Ω(SII(SII))SI)(KI)I=KI(Ω(SII(SII))SIの出力結果は上の計算よりIになる)

実はこのΩはとても厄介な性質を持っていて、Ωの引数xの中にΩを含む式を入れると、この式が無限ループするなら式を出力し、何らかの式を出力するなら無限ループする、という関数が作れてしまいます。
もう少し分かりやすい言い方をすると、"この文は間違っている"みたいなものが作れます。
これは矛盾が生じるので、そのような式は出力結果が存在しないとして、無視されます。
そしてクサイ関数$\Xi (n)$は、S,K,I,Ωの4種類の文字からなる$n$文字の式の出力サイズの最大値と定義されます。

$\Xi (7)$までの、出力サイズが最大になる最初の式を置いておきます。

$n=1$ : S
$n=2$ : S(S)
$n=3$ : S(SS)
$n=4$ : S(SSS)
$n=5$ : SSS(SI)
$n=6$ : SSS(SI)S
$n=7$ : SSS(SI)SΩ

さて、この関数がなぜLv.2、ビジービーバー関数より大きいのか。
それは簡単です。
神託コンビネータΩの存在です。
このΩは、無限ループするかどうかをすぐに教えてくれます。
なので、有限の文字数と有限の時間でビジービーバー関数をシミュレーションできます。
そして、逆にビジービーバー関数で使ったチューリングマシンでは、Ωを有限の時間でシミュレーションできません。
なので関数の強さが比較でき、こちらの方が大きい言えます。
つまり、ΩがないただのSKIコンビネータ計算だと関数の強さは同じになります。

さて、まだまだ続きます。
次はL.3?です。

レベル 計算不能Lv.3?:ラヨ関数

Lv.3の後ろに？がついていますが、今から説明する関数の定義は、厳密に考えると問題があります。
ぜひ数学オタクの人は、自分でいろいろ調べてみて、どこが問題なのか考えてみてください。
では定義です。

$Rayo(n)=$（一階の集合論（一階述語論理）の言葉で$n$個以内の記号で表現できるいかなる有限の正の整数よりも大きな最小の正の整数）
そしてラヨ数を$Rayo(10^{100})$とする。

もういろいろひどい定義ですね。
最初から一階述語論理とかなんとか、一体何を言っているのかわかりませんよね？
ざっくり説明すると、一階述語論理とは数学のほぼすべてを表現できる数学の言語、と考えて下さい。
つまり、この関数はほぼすべての数学を対角化しています！
もうなんだかすごいですよね！
もうここら辺まで来ると、詳細を書いても誰も読まなくなるので、さっさと次の関数に行って終わらせちゃいましょう。（別に自分が分かってないって意味じゃないからね！）

レベル 計算不能Lv.4:巨大数庭園数

これは、ニンゲンジャナイP進大好きbot様によって定義された数です。
関数には名前がついていないので、数の名前の略称を載せました。
えっ？本当の名前はなんだって？
ヤツの本当の名は...
「さあ盟友、ついに巨大数庭園の完成だ！　この庭園の機能を説明しよう。まず１つ目は住所と間取り図の判定機能。文字列を読み込むと、それがどの箱庭の住所を表しているかやどの箱庭で再現可能な巨大数庭園の間取り図なのかを自動で判定してくれるんだ。次に２つ目が間取り図の解析機能。箱庭の住所を指定してそこで再現可能な巨大数庭園の間取り図を読み込むと、その庭園が生み出せる巨大数を教えてくれるのさ。そして肝心の３つ目の機能が巨大数の生成機能。ひとたび自然数を入力すると、それを文字数の上限とした範囲内にある全文字列を探索し、それぞれを住所と間取り図の判定機能に読み込ませることで箱庭ごとに再現可能な間取り図のみを残して列挙し、更に間取り図の解析機能に読み込ませることでそれらが生み出せる巨大数を入手し、それら全てをまとめ上げることで新たな巨大数を生み出せるんだ！　え？　それで本当に巨大な数が得られるのかって？　相変わらず盟友は疑り深いなあ。でもいいさ、この巨大数庭園自体の間取り図がここにある。これを解析機能に読み込ませれば、どれほど巨大な数を生み出せるのかを教えてくれるからね。え？　この間取り図の文字数？　そんなものを知って何になるんだい？」
だっ...！！
長い！！

この関数は一体何をやっているのかを、読んでくれそうなくらい簡単に説明すると、ラヨ関数では一階述語論理という数学の言語を使ったけど、これで表現できるのは"ほぼ"すべての数学なら、もっといろいろ表現できる言語を作って、それそのものも対角化して、それを何回か繰り返してしまおう！...みたいな感じ...のハズデス。ハイ。
実は自分もよくわかってません。
しかし、この巨大数庭園数は、世界中の人がいる巨大数界隈で、今のところ最も大きい数として認識されています。
そう！実質的に世界で一番デカい数が！日本の！しかもタラーが！作ったのです！
なんかいいですねぇ..

以上で巨大数の話を終わります。
ちゃんと最後まで読んだあなたはきっと数学オタクです。

明日のアドベントカレンダーは@comaviusが担当します！お楽しみに！