爆発木関数は急増加する巨大関数である[1]

定義

Tをmの左へ行く枝とnの右へ行く枝を持つ二分木とする。\(p\)をある数とし、二つの変形のルールを決める:

  • Tと(n+p)の長さを持つ枝を取り除く。
  • 新しい部分木のそれぞれの(n+p)の枝に、長さ(m-1)の枝をその左の子として取り付ける。

この関数は、その部分木が右へ行く枝のみになった場合のみ、決定される。

木を完全に描くことは現実的ではないため、f(xLnR,m)xの左向きの枝の"長さ"とnの左向きの枝の"length"と定数mによる完全な変形された木とする。そしてE(n) = f(nL0R,n)である。

\( E(0) = 0 \)
\( E(1) = 1 \)
\( E(2) = 2 \)
\( E(3) = 6561 \)
\( E(4) > 4 \uparrow^{4 \uparrow\uparrow 4} 4 = \{4,4,\{4,4,2\}\} > \{4,2,1,2\} \)
\( E(5) > \{5,5,\{5,5,\{5,5,3\}\}\} > \{5,3,1,2\} \)
\( E(6) > \{6,6,\{6,6,\{6,6,\{6,6,4\}\}\}\} > \{6,4,1,2\} \)

一般的に \( E(n) > \{n,n-2,1,2\} \) が成立することが2021年6月9日まで英語版で事実とされてきた[2]が、ソースはなく証明が書かれてもいない。

他の関数との比較

「急増加関数においてE(n)は\(f_{\omega+1}(n)\)と近似されるので膨張関数と同等の増加率を持つ」ということが2021年6月9日まで英語版で事実とされてきた[2]が、ソースはなく証明が書かれてもいない。

出典

特に記載のない限り、コミュニティのコンテンツはCC-BY-SAライセンスの下で利用可能です。