FANDOM


急増加関数 (FGH; Fast-growing hierarchy)[1][2]は、順序数αに対して自然数から自然数への関数\(f_\alpha(n)\)を定める順序数による関数の階層である。関数の大きさを評価、比較する時によく用いられる。

通常は、次のように定義される。

  • \(f_0(n) = n + 1\)
  • \(f_{\alpha+1}(n) = f^n_\alpha(n)\)
  • \(f_\alpha(n) = f_{\alpha[n]}(n)\)

ここで、\(\alpha[n]\) は、極限順序数 \(\alpha\) の基本列の\(n\)番目である。

一般の単調増加関数 \(f_0\) に対する階層は 急反復関数 (fast iteration hierarchy) である。

\(\alpha[n]\) は順序数 \(\alpha\)に対する収束列の \(n\)番目の項である。 収束列 \(\alpha[n]\) の定義は一通りではなく、収束列の定義によって異なる急増加関数が得られる。\(\alpha \leq \epsilon_0\)に対して、いわゆるWainer 階層は次のように定義される。

  1. \(\omega[n] = n\)
  2. \(\omega^{\alpha + 1}[n] = \omega^\alpha n\)
  3. \(\omega^{\alpha}[n] = \omega^{\alpha[n]}\) (\(\alpha\) が極限順序数の時かつその時に限り)
  4. \((\omega^{\alpha_1} + \omega^{\alpha_2} + \cdots + \omega^{\alpha_{k - 1}} + \omega^{\alpha_k})[n] = \omega^{\alpha_1} + \omega^{\alpha_2} + \cdots + \omega^{\alpha_{k - 1}} + \omega^{\alpha_k}[n]\) (\(\alpha_1 \geq \alpha_2 \geq \cdots \geq \alpha_{k - 1} \geq \alpha_k\) の場合)
  5. \(\epsilon_0[0] = 0\) (もしくは \(1\)) かつ \(\epsilon_0[n + 1] = \omega^{\epsilon_0[n]}\)

たとえば、

\begin{align*}\omega^\omega [n] &= \omega^{\omega[n]} \quad \text{(3.を用いた)}\\&= \omega^n \quad \text{(1.を用いた)}\end{align*}

であるから、\(\omega^\omega\)に対する収束列は\(1, \omega, \omega^2, \omega^3, \ldots\) である。また、

\begin{align*}\left(\omega^{\omega^{\omega^\omega}} + \omega^{\omega^{\omega^2+2}} \right)\, [n] &= \omega^{\omega^{\omega^\omega}} + \omega^{\omega^{\omega^2+2}} [n] \quad \text{(4.を用いた)}\\ &= \omega^{\omega^{\omega^\omega}} + \omega^{(\omega^{\omega^2+2}\ )\ [n]} \quad \text{(3.を用いた)} \\&=\omega^{\omega^{\omega^\omega}} + \omega^{(\omega^{(\omega^2+1) +1}\ \ ) \ [n]}\\ &= \omega^{\omega^{\omega^\omega}} + \omega^{(\omega^{\omega^2+1}\ )\ n} \quad \text{(2.を用いた)} \end{align*}

であるから、\(\omega^{\omega^{\omega^\omega}} + \omega^{\omega^{\omega^2+2}} \)に対する収束列は \(\omega^{\omega^{\omega^\omega}} +1, \omega^{\omega^{\omega^\omega}} + \omega^{(\omega^{\omega^2+1} )} ,\ \omega^{\omega^{\omega^\omega}} + \omega^{(\omega^{\omega^2+1}) 2} ,\ \omega^{\omega^{\omega^\omega}} + \omega^{(\omega^{\omega^2+1}) 3} ,\ \ldots\) である。

Wainer 階層は Veblen functionフェファーマン・シュッテの順序数 \(\Gamma_0\) にまで拡張できる。収束列が定義される限り、急増加関数を帰納的順序数を通して、 \(\omega_1^\text{CK}\) (チャーチ・クリーネ順序数) にまで拡張することができる。急増加関数が帰納的でない順序数に拡張できるか、そしてもしできるとすればそれは何を意味するかは、未解決の問題である。

近似 編集

以下に、いくつかの Wainer 階層による関数と、巨大数で使われる表記との比較をする。

いくつか、気をつけることがある。

  • \(f_\alpha(n) > g(n)\) と書かれているときに、その関係は十分に大きい \(n\) に対して成り立つことを意味し、すべての \(n\) に対して成り立つとは限らない。.
  • \(m\) は任意の正の整数である。
  • \(m\alpha\) は、ここでは \(\alpha \times m = \underbrace{\alpha + \cdots + \alpha}_m\) の省略である。標準的な順序数の計算では、\(\alpha\) が極限順序数で\(1 < m < \omega\)の時、\(m \times \alpha \neq \alpha \times m\)である。
  • \(^ab\) は テトレーションを意味する。
  • \(\uparrow\) は矢印表記を意味する。
  • \(\text{A}\) は多変数アッカーマン関数を意味する。
  • \(\lbrace \rbrace\) はBEAFである。
  • \(X\) という表記は構造を意味する。

\(ε_0\) まで 編集

\begin{eqnarray*} f_0(n) &=& n + 1 \\ f_1(n) &=& f_0^n(n) = ( \cdots ((n + 1) + 1) + \cdots + 1) = n + n = 2n \\ f_2(n) &=& f_1^n(n) = 2(2(\ldots 2(2n))) = 2^n n > 2 \uparrow n \\ f_3(n) &>& 2\uparrow\uparrow n \\ f_4(n) &>& 2\uparrow\uparrow\uparrow n \\ f_m(n) &>& 2\uparrow^{m-1} n \\ f_\omega(n) &>& 2\uparrow^{n-1} n = A(n,n) \\ f_{\omega+1}(n) &>& \lbrace n,n,1,2 \rbrace \approx A(1,1,n) \\ f_{\omega+2}(n) &>& \lbrace n,n,2,2 \rbrace \approx A(1,2,n) \\ f_{\omega+m}(n) &>& \lbrace n,n,m,2 \rbrace \approx A(1,m,n) \\ f_{\omega2}(n) &>& \lbrace n,n,n,2 \rbrace \approx A(2,0,n) \\ f_{\omega3}(n) &>& \lbrace n,n,n,3 \rbrace \approx A(3,0,n) \\ f_{\omega m}(n) &>& \lbrace n,n,n,m \rbrace \approx A(m,0,n) \\ f_{\omega^2}(n) &>& \lbrace n,n,n,n \rbrace = \lbrace n,2,1,1,2 \rbrace \approx A(1,0,0,n) \\ f_{\omega^3}(n) &>& \lbrace n,n,n,n,n \rbrace = \lbrace n,2,1,1,1,2 \rbrace \approx A(1,0,0,0,n) \\ f_{... + \omega^3 a_3 + \omega^2 a_2 + \omega a_1 + a_0}(n) &>& \lbrace n,2,a_0+1,a_1+1,a_2+1,a_3+1,... \rbrace \approx A(..., a_3, a_2, a_1, a_0, n) \\ f_{\omega^m}(n) &>& \lbrace n,m+2 (1) 2 \rbrace \\ f_{\omega^{\omega}}(n) &>& \lbrace n,n+2 (1) 2 \rbrace > \lbrace n,n (1) 2 \rbrace \\ f_{\omega^{\omega}+1}(n) &>& \lbrace n,n,2 (1) 2 \rbrace \\ f_{\omega^{\omega}+2}(n) &>& \lbrace n,n,3 (1) 2 \rbrace \\ f_{\omega^{\omega}+m}(n) &>& \lbrace n,n,m+1 (1) 2 \rbrace \\ f_{\omega^{\omega}+\omega}(n) &>& \lbrace n,n,n+1 (1) 2 \rbrace > \lbrace n,n,n (1) 2 \rbrace \\ f_{\omega^{\omega}+\omega+1}(n) &>& \lbrace n,n,1,2 (1) 2 \rbrace \\ f_{\omega^{\omega}+\omega2}(n) &>& \lbrace n,n,n,2 (1) 2 \rbrace \\ f_{\omega^{\omega}+\omega^2}(n) &>& \lbrace n,n,n,n (1) 2 \rbrace \\ f_{{\omega^{\omega}}2}(n) &>& \lbrace n,n (1) 3 \rbrace \\ f_{{\omega^{\omega}}3}(n) &>& \lbrace n,n (1) 4 \rbrace \\ f_{{\omega^{\omega}}m}(n) &>& \lbrace n,n (1) m+1 \rbrace \\ f_{\omega^{\omega+1}}(n) &>& \lbrace n,n (1) n+1 \rbrace > \lbrace n,n (1) n \rbrace \\ f_{\omega^{\omega+2}}(n) &>& \lbrace n,n (1) n,n \rbrace \\ f_{\omega^{\omega+3}}(n) &>& \lbrace n,n,n (1) n,n,n \rbrace \\ f_{\omega^{\omega+m}}(n) &>& \lbrace n,m (1)(1) 2 \rbrace \\ f_{\omega^{\omega2}}(n) &>& \lbrace n,n (1)(1) 2 \rbrace = \lbrace n,2 (2) 2 \rbrace \\ f_{\omega^{\omega3}}(n) &>& \lbrace n,n (1)(1)(1) 2 \rbrace = \lbrace n,3 (2) 2 \rbrace \\ f_{\omega^{\omega m}}(n) &>& \lbrace n,m (2) 2 \rbrace \\ f_{\omega^{\omega^2}}(n) &>& \lbrace n,n (2) 2 \rbrace \\ f_{\omega^{\omega^3}}(n) &>& \lbrace n,n (3) 2 \rbrace \\ f_{\omega^{\omega^m}}(n) &>& \lbrace n,n (m) 2 \rbrace \\ f_{\omega^{\omega^\omega}}(n) &>& \lbrace n,n (n) 2 \rbrace = \lbrace n,n (0,1) 2 \rbrace \\ f_{^4{\omega}}(n) &>& \lbrace n,n ((1) 1) 2 \rbrace = n \uparrow\uparrow 3 \&\ n \\ f_{^5{\omega}}(n) &>& \lbrace n,n ((0,1) 1) 2 \rbrace = n \uparrow\uparrow 4 \&\ n \\ f_{^6{\omega}}(n) &>& \lbrace n,n (((1) 1) 1) 2 \rbrace = n \uparrow\uparrow 5 \&\ n \\ f_{^m{\omega}}(n) &>& X \uparrow\uparrow m-1 \&\ n \\ f_{\varepsilon_0}(n) &>& X \uparrow\uparrow n-1 \&\ n \end{eqnarray*}

\(\varepsilon_0\) から\(\Gamma_0\) まで 編集

ここでは、\(\approx\)はおおよその比較を示し、 2つの関数が似た成長率を持つことを意味する。

\begin{eqnarray*} f_{\varepsilon^{\varepsilon_0}_0}(n) &\approx& X \uparrow\uparrow (X+1) \&\ n \\ f_{\varepsilon^{\varepsilon^{\varepsilon_0}_0}_0}(n) &\approx& X \uparrow\uparrow (X+2) \&\ n \\ f_{\varepsilon_1}(n) &\approx& X \uparrow\uparrow (2X) \&\ n \\ f_{\varepsilon_2}(n) &\approx& X \uparrow\uparrow (3X) \&\ n \\ f_{\varepsilon_\omega}(n) &\approx& X \uparrow\uparrow (X^2) \&\ n \\ f_{\varepsilon_{\omega2}}(n) &\approx& X \uparrow\uparrow (2X^2) \&\ n \\ f_{\varepsilon_{\omega^2}}(n) &\approx& X \uparrow\uparrow (X^3) \&\ n \\ f_{\varepsilon_{\omega^\omega}}(n) &\approx& X \uparrow\uparrow (X^X) \&\ n \\ f_{\varepsilon_{\varepsilon_0}}(n) &\approx& X \uparrow\uparrow (X \uparrow\uparrow X) \&\ n \\ f_{ζ_0}(n) &\approx& X \uparrow\uparrow\uparrow X \&\ n \\ f_{η_0}(n) &\approx& X \uparrow^{4} X \&\ n \\ f_{\varphi(m,0)}(n) &\approx& X \uparrow^{m+1} X \&\ n > n \uparrow^{m} \&\ n \\ f_{\varphi(\omega,0)}(n) &\approx& X \uparrow^{n+1} X \&\ n > X \uparrow^{X} \&\ X = \lbrace n,2,1,2 \rbrace \&\ n \\ f_{\varphi(\omega+1,0)}(n) &\approx& \lbrace X,X,X+1 \rbrace \&\ n \\ f_{\varphi(\omega+2,0)}(n) &\approx& \lbrace X,X,X+2 \rbrace \&\ n \\ f_{\varphi(\omega2,0)}(n) &\approx& \lbrace X,X,2X \rbrace \&\ n \\ f_{\varphi(\omega3,0)}(n) &\approx& \lbrace X,X,3X \rbrace \&\ n \\ f_{\varphi(\omega^2,0)}(n) &\approx& \lbrace X,X,X^2 \rbrace \&\ n \\ f_{\varphi(\omega^3,0)}(n) &\approx& \lbrace X,X,X^3 \rbrace \&\ n \\ f_{\varphi(\omega^\omega,0)}(n) &\approx& \lbrace X,X,X^X \rbrace \&\ n \\ f_{\varphi(\omega^{\omega2},0)}(n) &\approx& \lbrace X,X,X^{2X} \rbrace \&\ n \\ f_{\varphi(\omega^{\omega3},0)}(n) &\approx& \lbrace X,X,X^{3X} \rbrace \&\ n \\ f_{\varphi(\omega^{\omega^2},0)}(n) &\approx& \lbrace X,X,X^{X^2} \rbrace \&\ n \\ f_{\varphi(\omega^{\omega^3},0)}(n) &\approx& \lbrace X,X,X^{X^3} \rbrace \&\ n \\ f_{\varphi(\omega^{\omega^\omega},0)}(n) &\approx& \lbrace X,X,X^{X^X} \rbrace \&\ n \\ f_{\varphi(\omega^{\omega^{\omega^\omega}},0)}(n) &\approx& \lbrace X,X,X^{X^{X^X}} \rbrace \&\ n \\ f_{\varphi(\varepsilon_0,0)}(n) &\approx& \lbrace X,X,X \uparrow\uparrow X \rbrace \&\ n \\ f_{\varphi(ζ_0,0)}(n) &\approx& \lbrace X,X,X \uparrow\uparrow\uparrow X \rbrace \&\ n \\ f_{\varphi(η_0,0)}(n) &\approx& \lbrace X,X,X \uparrow^{4} X \rbrace \&\ n \\ f_{\varphi(\varphi(\omega,0),0)}(n) &\approx& \lbrace X,X,X \uparrow^{X} X \rbrace \&\ n = \lbrace X,X, \lbrace X,X,X \rbrace\rbrace \&\ n \\ f_{\varphi(\varphi(\varphi(\omega,0),0),0)}(n) &\approx& \{X,4,1,2\} \&\ n \\ \end{eqnarray*}

\(\Gamma_0\) から \(\vartheta(\Omega^\Omega)\) まで 編集

\begin{eqnarray*} f_{Γ_0}(n) &\approx& \lbrace X,X,1,2 \rbrace \&\ n \\ f_{\varphi(Γ_0,1)}(n) &\approx& \lbrace X,X+1,1,2 \rbrace \&\ n \\ f_{Γ_1}(n) &\approx& \lbrace X,2X,1,2 \rbrace \&\ n \\ f_{Γ_2}(n) &\approx& \lbrace X,3X,1,2 \rbrace \&\ n \\ f_{Г_\omega}(n) &\approx& \lbrace X,X^2,1,2 \rbrace \&\ n \\ f_{Г_{Г_0}}(n) &\approx& \lbrace X,\lbrace X,X,1,2 \rbrace,1,2 \rbrace \&\ n \\ f_{\varphi(1,1,0)}(n) &\approx& \lbrace X,X,2,2 \rbrace \&\ n \\ f_{\varphi(1,2,0)}(n) &\approx& \lbrace X,X,3,2 \rbrace \&\ n \\ f_{\varphi(1,\omega,0)}(n) &\approx& \lbrace X,X,X,2 \rbrace \&\ n \\ f_{\varphi(1,\varphi(1,0,0),0)}(n) &\approx& \lbrace X,X,\lbrace X,X,1,2 \rbrace,2 \rbrace \&\ n \\ f_{\varphi(2,0,0)}(n) &\approx& \lbrace X,X,1,3 \rbrace \&\ n \\ f_{\varphi(3,0,0)}(n) &\approx& \lbrace X,X,1,4 \rbrace \&\ n \\ f_{\varphi(\omega,0,0)}(n) &\approx& \lbrace X,X,1,X \rbrace \&\ n \\ f_{\varphi(\varphi(1,0,0),0,0)}(n) &\approx& \lbrace X,X,1,\lbrace X,X,1,2 \rbrace\rbrace \&\ n \\ f_{\varphi(1,0,0,0)}(n) &\approx& \lbrace X,X,1,1,2 \rbrace \&\ n \\ f_{\varphi(2,0,0,0)}(n) &\approx& \lbrace X,X,1,1,3 \rbrace \&\ n \\ f_{\varphi(1,0,0,0,0)}(n) &\approx& \lbrace X,X,1,1,1,2 \rbrace \&\ n \\ f_{\vartheta(\Omega^\omega)}(n) &\approx& \lbrace X,X (1) 2 \rbrace \&\ n \\ f_{\vartheta(\Omega^{\omega+1})}(n) &\approx& \lbrace X,X+1 (1) 2 \rbrace \&\ n \\ f_{\vartheta(\Omega^{\omega+m})}(n) &\approx& \lbrace X,X+m (1) 2 \rbrace \&\ n \\ f_{\vartheta(\Omega^{\omega 2})}(n) &\approx& \lbrace X,2X (1) 2 \rbrace \&\ n \\ f_{\vartheta(\Omega^{\omega^2})}(n) &\approx& \lbrace X,X^2 (1) 2 \rbrace \&\ n \\ f_{\vartheta(\Omega^{\omega^\omega})}(n) &\approx& \lbrace X,X^X (1) 2 \rbrace \&\ n \\ f_{\vartheta(\Omega^{\varepsilon_0})}(n) &\approx& \lbrace X,X \uparrow\uparrow X (1) 2 \rbrace \&\ n \\ f_{\vartheta(\Omega^{\zeta_0})}(n) &\approx& \lbrace X,X \uparrow\uparrow\uparrow X (1) 2 \rbrace \&\ n \\ f_{\vartheta(\Omega^{\varphi(\omega,0)})}(n) &\approx& \lbrace X,\lbrace X,X,X \rbrace (1) 2 \rbrace \&\ n \\ f_{\vartheta(\Omega^{Γ_0})}(n) &\approx& \lbrace X,\lbrace X,X,1,2 \rbrace (1) 2 \rbrace \&\ n \\ f_{\vartheta(\Omega^{\vartheta(\Omega^\omega)})}(n) &\approx& \lbrace X,\lbrace X,X (1) 2 \rbrace (1) 2 \rbrace \&\ n \\ f_{\vartheta(\Omega^{\vartheta(\Omega^{\vartheta(\Omega^\omega)})})}(n) &\approx& \lbrace X,\lbrace X,\lbrace X,X (1) 2 \rbrace (1) 2 \rbrace (1) 2 \rbrace \&\ n \\ \end{eqnarray*}

\(\vartheta(\Omega^\Omega)\) から \(\vartheta(\varepsilon_{\Omega+1})\) まで 編集

\begin{eqnarray*} f_{\vartheta(\Omega^\Omega)}(n) &\approx& \{X,X,2(1)2\}\&n \\ f_{\vartheta(\Omega^{\vartheta(\Omega^\Omega)},\vartheta(\Omega^\Omega)+1)}(n) &\approx& \{X,X+1,2(1)2\}\&n \\ f_{\vartheta(\Omega^\Omega,1)}(n) &\approx& \{X,2X,2(1)2\}\&n \\ f_{\vartheta(\Omega^\Omega,\omega^\omega)}(n) &\approx& \{X,X^X,2(1)2\}\&n \\ f_{\vartheta(\Omega^\Omega,\vartheta(\Omega^\Omega))}(n) &\approx& \{X,3,3(1)2\}\&n \\ f_{\vartheta(\Omega^\Omega+1)}(n) &\approx& \{X,X,3(1)2\}\&n \\ f_{\vartheta(\Omega^\Omega+2)}(n) &\approx& \{X,X,4(1)2\}\&n \\ f_{\vartheta(\Omega^\Omega+\omega)}(n) &\approx& \{X,X,X(1)2\}\&n \\ f_{\vartheta(\Omega^\Omega+\Omega)}(n) &\approx& \{X,X,1,2(1)2\}\&n \\ f_{\vartheta(\Omega^\Omega+\Omega^2)}(n) &\approx& \{X,X,1,1,2(1)2\}\&n \\ f_{\vartheta(\Omega^\Omega+\Omega^\omega)}(n) &\approx& \{X,X(1)3\}\&n \\ f_{\vartheta(\Omega^\Omega2)}(n) &\approx& \{X,X,2(1)3\}\&n \\ f_{\vartheta(\Omega^\Omega3)}(n) &\approx& \{X,X,2(1)4\}\&n \\ f_{\vartheta(\Omega^\Omega\omega)}(n) &\approx& \{X,X(1)X\}\&n \\ f_{\vartheta(\Omega^{\Omega+1})}(n) &\approx& \{X,X(1)1,2\}\&n \\ f_{\vartheta(\Omega^{\Omega+1}+\Omega^\Omega)}(n) &\approx& \{X,X,2(1)2,2\}\&n \\ f_{\vartheta(\Omega^{\Omega+1}2)}(n) &\approx& \{X,X(1)1,3\}\&n \\ f_{\vartheta(\Omega^{\Omega+1}\omega)}(n) &\approx& \{X,X(1)X,X\}\&n \\ f_{\vartheta(\Omega^{\Omega+2})}(n) &\approx& \{X,X(1)1,1,2\}\&n \\ f_{\vartheta(\Omega^{\Omega+3})}(n) &\approx& \{X,X(1)1,1,1,2\}\&n \\ f_{\vartheta(\Omega^{\Omega+\omega})}(n) &\approx& \{X,X(1)(1)2\}\&n \\ f_{\vartheta(\Omega^{\Omega2})}(n) &\approx& \{X,X,2(1)(1)2\}\&n \\ f_{\vartheta(\Omega^{\Omega3})}(n) &\approx& \{X,X,2(1)(1)(1)2\}\&n \\ f_{\vartheta(\Omega^{\Omega\omega})}(n) &\approx& \{X,X(2)2\}\&n \\ f_{\vartheta(\Omega^{\Omega^2})}(n) &\approx& \{X,X,2(2)2\}\&n \\ f_{\vartheta(\Omega^{\Omega^22})}(n) &\approx& \{X,X,2(2)(2)2\}\&n \\ f_{\vartheta(\Omega^{\Omega^3})}(n) &\approx& \{X,X,2(3)2\}\&n \\ f_{\vartheta(\Omega^{\Omega^\Omega})}(n) &\approx& \{X,X,2(0,1)2\}\&n \\ f_{\vartheta(\Omega^{\Omega^{\Omega^\Omega}})}(n) &\approx& \{X,X,2((1)1)2\}\&n \\ \end{eqnarray*}

\(\vartheta(\varepsilon_{\Omega+1})\) から \(\vartheta(\Omega_\omega)\) まで 編集

\begin{eqnarray*} f_{\vartheta(\varepsilon_{\Omega+1})}(n) &\approx& X\uparrow\uparrow X\&X\&n \\ f_{\vartheta(\varepsilon_{\Omega2+1})}(n) &\approx& X\uparrow\uparrow(2X)\&X\&n \\ f_{\vartheta(\zeta_{\Omega+1})}(n) &\approx& X\uparrow\uparrow\uparrow X\&X\&n \\ f_{\vartheta(\varphi(\omega,\Omega+1))}(n) &\approx& \{X,X,X\}\&X\&n \\ f_{\vartheta(\Omega_2)}(n) &\approx& \{X,X,1,2\}\&X\&n \\ f_{\vartheta(\Omega_22)}(n) &\approx& \{X,X,1,3\}\&X\&n \\ f_{\vartheta(\Omega_2^2)}(n) &\approx& \{X,X,1,1,2\}\&X\&n \\ f_{\vartheta(\Omega_2^\omega)}(n) &\approx& \{X,X(1)2\}\&X\&n \\ f_{\vartheta(\Omega_2^{\Omega_2})}(n) &\approx& \{X,X,2(1)2\}\&X\&n \\ f_{\vartheta(\Omega_2^{\Omega_2}2)}(n) &\approx& \{X,X,2(1)3\}\&X\&n \\ f_{\vartheta(\Omega_2^{\Omega_2+1})}(n) &\approx& \{X,X,2(1)1,2\}\&X\&n \\ f_{\vartheta(\Omega_2^{\Omega_22})}(n) &\approx& \{X,X,2(1)(1)2\}\&X\&n \\ f_{\vartheta(\Omega_2^{\Omega_2^2})}(n) &\approx& \{X,X,2(2)2\}\&X\&n \\ f_{\vartheta(\Omega_2^{\Omega_2^{\Omega_2}})}(n) &\approx& \{X,X,2(0,1)2\}\&X\&n \\ f_{\vartheta(\varepsilon_{\Omega_2+1})}(n) &\approx& X\uparrow\uparrow X\&X\&X\&n \\ f_{\vartheta(\zeta_{\Omega_2+1})}(n) &\approx& X\uparrow\uparrow\uparrow X\&X\&X\&n \\ f_{\vartheta(\Omega_3)}(n) &\approx& \{X,X,1,2\}\&X\&X\&n \\ f_{\vartheta(\Omega_3^\omega)}(n) &\approx& X\&X\&X\&X\&n \\ f_{\vartheta(\Omega_4^\omega)}(n) &\approx& X\&X\&X\&X\&X\&n \\ \end{eqnarray*}

\(\vartheta(\Omega_\omega)\) から \(\vartheta(\Omega_\Omega)\) まで 編集

\begin{eqnarray*} f_{\vartheta(\Omega_\omega)}(n) &\approx& \{n,n/2\} \\ f_{\vartheta(\Omega_\omega)+1}(n) &\approx& \{n,n,2/2\} \\ f_{\vartheta(\Omega_\omega)+\omega}(n) &\approx& \{n,n,n/2\} \\ f_{\vartheta(\Omega_\omega)+\omega^\omega}(n) &\approx& \{n,n(1)2/2\} \\ f_{\vartheta(\Omega_\omega)2}(n) &\approx& \{n,n/3\} \\ f_{\vartheta(\Omega_\omega)\omega}(n) &\approx& \{n,n/n+1\} \\ f_{\vartheta(\Omega_\omega)(\omega+1)}(n) &\approx& \{n,n/1,2\} \\ f_{\vartheta(\Omega_\omega)(\omega+1)}(n) &\approx& \{n,n/1,2\} \\ f_{\vartheta(\Omega_\omega)(\omega^2+1)}(n) &\approx& \{n,n/1,1,2\} \\ f_{\vartheta(\Omega_\omega)(\omega^\omega)}(n) &\approx& \{n,n/1(1)2\} \\ f_{\vartheta(\Omega_\omega)^2}(n) &\approx& \{n,n/1/2\} \\ f_{\vartheta(\Omega_\omega)^\omega}(n) &\approx& \{n,n(/1)2\} \\ f_{\vartheta(\Omega_\omega)^{\omega^2}}(n) &\approx& \{n,n(/2)2\} \\ f_{\vartheta(\Omega_\omega)^{\varepsilon_0}}(n) &\approx& X \uparrow\uparrow X\text{&}\text{&}n \\ f_{\vartheta(\Omega_\omega)^{\vartheta(\Omega_\omega)}}(n) &\approx& \{X,X/2\}\text{&}\text{&}n \\ f_{\varepsilon_{\vartheta(\Omega_\omega)+1}}(n) &\approx& \{X,X/2\}\uparrow\uparrow X\text{&}\text{&}n\end{eqnarray*}

帰納的でない順序数 編集

急増加関数はすべての帰納的な順序数について定義することが可能であり、また、そうでない順序数についても可能である。しかしながら、その定義は必然的に非帰納的になり、解析ははるかに複雑になる。例えば、 \(F_{\omega_1^\text{CK}}(n)\) がすべての計算可能関数より速く増加するかどうかは自明ではなく、 \(\Sigma(n)\) の増加速度によって比較される。

The smallest non-recursive ordinal is \(\omega^\text{CK}_1\), the チャーチ・クリーネ順序数. BEAF, being a computable function, is completely exhausted by now. In order, the functions are ビジービーバー関数, its higher-order cousins, ラヨ関数, and the クサイ関数. Here \(\alpha\) is the first ordinal such that \(\omega^\text{CK}_{\alpha} = \alpha\).

\begin{eqnarray*} f_{\omega^\text{CK}_1}(n) &\approx& \Sigma(n) \\ f_{\omega^\text{CK}_2}(n) &\approx& \Sigma_2(n) \\ f_{\omega^\text{CK}_3}(n) &\approx& \Sigma_3(n) \\ f_{\omega^\text{CK}_m}(n) &\approx& \Sigma_m(n) \\ f_{\alpha}(n) &\approx& \Xi(n) \\ \end{eqnarray*}

Aeton の計算 編集

Aeton が、さらに近似精度を高めるための計算をしている[3]

\begin{eqnarray*} f_\omega(n) &<& (n+1)\uparrow^{n-1} (n+1) \\ f_{\omega+m}(n) &>& \lbrace n+1,n+1,m,2 \rbrace \\ f_{\omega^2}(n) &<& \lbrace n+1,n+1,n,n \rbrace \\ \end{eqnarray*}

関連項目 編集

参考サイト 編集

  1. 巨大数論
  2. Fast-growing hierarchy - Wikipedia
  3. [1]

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


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

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

FANDOMでも見てみる

おまかせWiki