Fandom

巨大数研究 Wiki

爆発木関数

549このwikiの
ページ数
新しいページをつくる
コメント0 シェアする
爆発木関数
Combinatorial
急増加関数 \(f_{\omega+1}(n)\)

爆発木関数は急増加する巨大関数である[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\} \)

他の関数との比較 編集

急増加関数においてE(n)は\(f_{\omega+1}(n)\)と近似されるので、膨張関数と同等の増加率を持つ。

出典 編集

  1. Exploding Tree Function

広告ブロッカーが検出されました。


広告収入で運営されている無料サイトWikiaでは、このたび広告ブロッカーをご利用の方向けの変更が加わりました。

広告ブロッカーが改変されている場合、Wikiaにアクセスしていただくことができなくなっています。カスタム広告ブロッカーを解除してご利用ください。

Fandomでも見てみる

おまかせWiki