はじめに[]
急増加関数は巨大数を学ぶ上で中級者の壁として立ちはだかる。急増加関数は様々な関数の強さをおおざっぱに表すのに便利で、巨大数研究Wikiの至るところに登場する。しかし、急増加関数をきちんと理解するためには順序数を学ばなければならないなど、とっつきにくさがあることは否定できない。そこで本記事は、なるべく順序数について触れずに急増加関数の概念について説明を試みる。
定義(\(f_n(x)\)まで)[]
急増加関数とは、次の漸化式で与えられる関数列である。
- \(f_0(x)=x+1\)
- \(f_{n+1}(x)=f^x_n(x)\)
例えば\(f_1(x)=2x\)であり、\(f_2(x)=2^x x\)である。
一般には\(f_m(x) \approx 2\uparrow^{m-1} x\)が成り立つ。
\(f_\omega (x)\)への到達[]
ではここで、\(f_m(x)\)の添え字\(m\)を変数化してみよう。このとき作られる関数\(f_x(x) \approx 2\uparrow^{x-1} x\)は急増加関数の１つの区切りとなる地点である。\(f_x(x)\)は足し算、掛け算、べき乗を有限回組み合わせたり、合成したりしてつくられるいかなる関数（これを原始再帰関数という）よりも増加速度が大きいことが知られている。変数\(x\)はかっこの中だけにあった方が分かりやすい形なので、本家の急増加関数では、この\(f_x(x)\)の強さを\(f_\omega (x)\)と表記する。
\(f_\omega (x)\)クラスの関数の例[]
アッカーマン関数\(A(a,b)\)は矢印表記で\(2\uparrow^{a-2} (b+3)-3\)と書き換えられる関数であり、↑の数を変数化しているという点から、ほぼ\(f_\omega (x)\)の強さの関数と考えることができる。
また、グラハム数の定義で登場した関数\(g(x)=3\uparrow^x 3\)もほぼ\(f_\omega (x)\)の強さである。
\(\omega\)とは何か？なぜ\(\omega\)を使うのか？[]
\(\omega\)は極限順序数と呼ばれ、自然数の列１，２，３，...の極限のことである。つまり、\(\omega\)はすべての自然数よりも大きな存在、無限と考えて差し支えない。しかし、この記事の読者の中には「巨大数は有限の自然数について考察する場なのに、どうして無限が出てくるのか？」といった疑問を持つ方もいるだろう。
例えば、関数\(f(x)=x^m\)について考えてみよう。言うまでもなく、この関数は\(m\)の値が大きな方が強力な関数となる。しかし、どれだけ\(m\)を大きくしても\(2^x\)といった関数に増加速度で負けてしまうのだ。つまり、「\(2^x\)の強さは\(x^m\)で例えるとどのくらいの\(m\)が相当するか？」といった質問に対しては「\(m\)が無限のとき」としか答えようがないのだ。これと同じように、「アッカーマン関数は急増化関数\(f_m(x)\)でいうとどのくらいの\(m\)が相当するか？」といった質問には\(\omega\)を使うしか回答のしようがないのだ。
\(f_\omega (x)\)のその先へ[]
急増加関数は\(f_\omega (x)\)より強い関数を生み出せないのだろうか？もちろんそんなことはない。例えば、\(f_\omega (x) \approx 2\uparrow^x x\)を\(x\)重にした\(f_\omega ^x (x)\)は\(f_\omega (x)\)よりも強い。この関数の強さは\(f_{\omega+1} (x)\)と表すことができる。急増加関数の良いところは、添え字の部分に特殊な表記を使うことを許す代わりに、最初の定義を変えることなく大きな関数を表現できる点である。ある巨大な関数を急増加関数で近似することができたら、添え字の部分だけを見ることでその関数のおおよその強さを把握することができるのだ。