急増加関数のざっくりとした説明

はじめに

急増加関数は巨大数を学ぶ上で中級者の壁として立ちはだかる。急増加関数は様々な関数の強さをおおざっぱに表すのに便利で、巨大数研究Wikiの至るところに登場する。しかし、急増加関数をきちんと理解するためには順序数を学ばなければならないなど、とっつきにくさがあることは否定できない。そこで本記事は、なるべく順序数について触れずに急増加関数の概念について説明を試みる。

ざっくりとした定義

急増加関数とは、おおざっぱに言えば次の漸化式で与えられる関数列である。

• f0(x)=x+1$f_0(x)=x+1$

• fn+1(x)=fxn(x)$f_{n+1}(x)=f_n^x(x)$

例えばf1(x)=2x$f_1(x)=2x$であり、f2(x)=2xx$f_2(x)=2^{x}x$である。

一般にはfm(x)≈2↑m−1x$f_m(x)\approx 2{\uparrow }^{m-1}x$が成り立つ。

fω(x)$f_{\omega }(x)$への到達

ではここで、fm(x)$f_m(x)$の添え字m$m$を変数化してみよう。このとき作られる関数fx(x)≈2↑x−1x$f_x(x)\approx 2{\uparrow }^{x-1}x$は急増加関数の１つの区切りとなる地点である。fx(x)$f_x(x)$は足し算、掛け算、べき乗を有限回組み合わせたり、合成したりしてつくられるいかなる関数（これを原始再帰関数という）よりも増加速度が大きいことが知られている。変数x$x$はかっこの中だけにあった方が分かりやすい形なので、本家の急増加関数では、このfx(x)$f_x(x)$の強さをfω(x)$f_{\omega }(x)$と表記する。

fω(x)$f_{\omega }(x)$クラスの関数の例

アッカーマン関数A(a,b)$A(a,b)$は矢印表記で2↑a−2(b+3)−3$2{\uparrow }^{a-2}(b+3)-3$と書き換えられる関数であり、↑の数を変数化しているという点から、ほぼfω(x)$f_{\omega }(x)$の強さの関数と考えることができる。

また、グラハム数の定義で登場した関数g(x)=3↑x3$g(x)=3{\uparrow }^{x}3$もほぼfω(x)$f_{\omega }(x)$の強さである。

ω$\omega$とは何か？なぜω$\omega$を使うのか？

ω$\omega$は極限順序数と呼ばれ、自然数の列１，２，３，...の極限のことである。つまり、ω$\omega$はすべての自然数よりも大きな存在、無限と考えて差し支えない。しかし、この記事の読者の中には「巨大数は有限の自然数について考察する場なのに、どうして無限が出てくるのか？」といった疑問を持つ方もいるだろう。

例えば、関数f(x)=xm$f(x)=x^m$について考えてみよう。言うまでもなく、この関数はm$m$の値が大きな方が強力な関数となる。しかし、どれだけm$m$を大きくしても2x$2^x$といった関数に増加速度で負けてしまうのだ。つまり、「2x$2^x$の強さはxm$x^m$で例えるとどのくらいのm$m$が相当するか？」といった質問に対しては「m$m$が無限のとき」としか答えようがないのだ。これと同じように、「アッカーマン関数は急増化関数fm(x)$f_m(x)$でいうとどのくらいのm$m$が相当するか？」といった質問にはω$\omega$を使うしか回答のしようがないのだ。

fω(x)$f_{\omega }(x)$のその先へ

急増加関数はfω(x)$f_{\omega }(x)$より強い関数を生み出せないのだろうか？もちろんそんなことはない。例えば、fω(x)≈2↑xx$f_{\omega }(x)\approx 2{\uparrow }^{x}x$をx$x$重にしたfxω(x)$f_{\omega }^x(x)$はfω(x)$f_{\omega }(x)$よりも強い。この関数の強さはfω+1(x)$f_{\omega +1}(x)$と表すことができる。急増加関数の良いところは、添え字の部分に特殊な表記を使うことを許す代わりに、最初の定義を変えることなく大きな関数を表現できる点である。ある巨大な関数を急増加関数で近似することができたら、添え字の部分だけを見ることでその関数のおおよその強さを把握することができるのだ。