Быстрорастущая иерархия

Быстрорастущая иерархия (также называемая расширенной иерархией Гржегорчика) — это семейство быстрорастущих функций, индексированных ординалами. Наиболее известным частным случаем быстрорастущей иерархии является иерархия Лёба-Вайнера.

Определение

Быстрорастущая иерархия определяется следующими правилами

[math]\displaystyle{ f_0(n)=n+1 }[/math] (в общем случае [math]\displaystyle{ f_0(n) }[/math] может быть любой растущей функцией),
[math]\displaystyle{ f_{\alpha+1}(n)= f_\alpha^n(n)=\underbrace{f_{\alpha}(f_{\alpha}(\cdots(f_{\alpha}(f_{\alpha}(}_{n\mbox{ раз}}n))\cdots)) }[/math],
[math]\displaystyle{ f_\alpha(n)= f_{\alpha[n]}(n) }[/math] если [math]\displaystyle{ \alpha }[/math] предельный ординал,
- где [math]\displaystyle{ \alpha[n] }[/math] является n-м элементом фундаментальной последовательности, установленной для некого предельного ординала [math]\displaystyle{ \alpha }[/math].
- Существуют различные версии быстрорастущей иерархии, однако наиболее известной является иерархия Лёба-Вайнера, в которой фундаментальные последовательности для предельных ординалов, записанных в нормальной форме Кантора, определяются следующими правилами:
[math]\displaystyle{ \omega[n]=n }[/math],
[math]\displaystyle{ (\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] }[/math]
- для [math]\displaystyle{ \alpha_1 \ge \alpha_2 \ge \cdots \ge \alpha_k }[/math],
[math]\displaystyle{ \omega^{\alpha+1}[n]=\omega^{\alpha}n }[/math],
[math]\displaystyle{ \omega^{\alpha}[n]=\omega^{\alpha[n]} }[/math] если [math]\displaystyle{ \alpha }[/math] предельный ординал,
[math]\displaystyle{ \varepsilon_0[0]=0 }[/math] и [math]\displaystyle{ \varepsilon_0 [n+1]=\omega^{\varepsilon_0[n]}=\omega\uparrow \uparrow n }[/math].

Фундаментальные последовательности для предельных ординалов свыше [math]\displaystyle{ \varepsilon_0 }[/math] приведены в статьях о функциях Веблена и функциях Бухгольца

Примеры

[math]\displaystyle{ f_1 (n)=f_0^n(n)=\underbrace{f_0(f_0(\cdots(f_0(f_0(}_{n \quad f_0}n))\cdots))=2\times n }[/math],

[math]\displaystyle{ f_2 (n)=f_1^n(n)=\underbrace{f_1(f_1(\cdots(f_1(f_1(}_{n \quad f_1}n))\cdots))=2^n \times n }[/math].

Для функций, индексированных конечными ординалами [math]\displaystyle{ \alpha \gt 1 }[/math] верно

[math]\displaystyle{ f_{m}(n) \gt 2 \uparrow^{m-1} n }[/math].

В частности, при n=10:

[math]\displaystyle{ f_3(10)=f_2^{10}(10)\approx\underbrace{10^{10^{10^{\cdots{^{10^{10^{3.489}}}}}}}}_{10 \quad \text {десяток} } \approx 10\uparrow\uparrow 11 }[/math],

[math]\displaystyle{ f_4(10)=f_3^{10}(10)\approx \left. \begin{matrix} &&\underbrace{10^{10^{10^{\cdots{^{10^{10^{3.489}}}}}}}}\\ & &\underbrace{10^{10^{10^{\cdots{^{10^{10^{3.489}}}}}}}}\\ & & \underbrace{\qquad \;\; \vdots \qquad\;\;}\\ & &\underbrace{10^{10^{10^{\cdots{^{10^{10^{3.489}}}}}}}}\\ & &10 \quad \text {десяток} \end{matrix} \right \} \text {10 нижних фигурных скобок} \approx 10\uparrow\uparrow\uparrow 11 }[/math],

[math]\displaystyle{ f_{m}(10) \approx 10 \uparrow^{m-1} 11 }[/math].

Таким образом, уже первый трансфинитный ординал [math]\displaystyle{ \omega }[/math] соответствует пределу стрелочной нотации Кнута.

Знаменитое число Грэма меньше, чем [math]\displaystyle{ f_{\omega+1}(64) }[/math].

Благодаря простоте и ясности определения быстрорастущая иерархия применяется для анализа различных нотаций для записи больших чисел.

	нотация Кнута	нотация Конвея	нотация Бауэрса
предел нотации	[math]\displaystyle{ \omega }[/math]	[math]\displaystyle{ \omega^2 }[/math]	[math]\displaystyle{ \omega^\omega }[/math]
примеры	[math]\displaystyle{ f_{\omega}(10) \approx 10 \uparrow^{9} 11 =10 \uparrow \uparrow\uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \uparrow 11 }[/math]	[math]\displaystyle{ f_{\omega^2}(n)\approx \underbrace{n\rightarrow n \rightarrow n\cdots \rightarrow n}_{n+1 \quad \rightarrow} }[/math]	[math]\displaystyle{ f_{\omega^\omega}(n) \approx \underbrace{\{n,n,n, \cdots,n,n\}}_{n+2 \quad n's} }[/math]
примеры	[math]\displaystyle{ f_{\omega+1}(10) \approx \left. \begin{matrix} &&\underbrace{10\uparrow\uparrow\cdots\uparrow\uparrow 11}\\ & &\underbrace{10\uparrow\uparrow\cdots\uparrow\uparrow 11} \\ & & \underbrace{\quad\quad \;\; \vdots \quad\quad\;\;}\\ & &\underbrace{10\uparrow\uparrow\cdots\uparrow\uparrow 11} \\ & &\text {9 стрелок} \end{matrix} \right \} \text {10} }[/math]	[math]\displaystyle{ f_{\omega^2+1}(n) \approx \left. \begin{matrix} &&\underbrace{n\rightarrow n\rightarrow\cdots n\rightarrow n}\\ & &\underbrace{n\rightarrow n\rightarrow\cdots n\rightarrow n} \\ & & \underbrace{\quad\quad\quad \;\; \vdots \quad\quad\quad\;\;}\\ & &\underbrace{n\rightarrow n\rightarrow\cdots n\rightarrow n} \\ & &\text {n+1 стрелка} \end{matrix} \right \} \text {n} }[/math]	[math]\displaystyle{ f_{\omega^\omega+1}(n) \approx \left. \begin{matrix} &&\underbrace{\{n,n,n, \cdots,n,n\}}\\ & &\underbrace{\{n,n,n, \cdots,n,n\}} \\ & & \underbrace{\quad\quad\quad \;\; \vdots \quad\quad\quad\;\;}\\ & &\underbrace{\{n,n,n, \cdots,n,n\}} \\ & &\text {n+2 n's} \end{matrix} \right \} \text {n} }[/math]

Данная выше дефиниция определяет быстрорастущую иерархию до [math]\displaystyle{ \varepsilon_0=\omega \uparrow \uparrow n }[/math]. Для дальнейшего роста можно использовать функцию Веблена и другие, еще более мощные нотации для ординалов^[1].

Примеры

[math]\displaystyle{ f_0(n) = n + 1 }[/math]
[math]\displaystyle{ f_1(n) = 2n }[/math]
[math]\displaystyle{ f_2(n) = 2^nn }[/math]
[math]\displaystyle{ f_3(n) \gt 2 \uparrow\uparrow n }[/math] (см. Стрелочная нотация Кнута)
[math]\displaystyle{ f_4(n) \gt 2 \uparrow\uparrow\uparrow n }[/math]
[math]\displaystyle{ f_m(n) \gt 2 \uparrow^{m-1} n }[/math]
[math]\displaystyle{ f_\omega(n) \gt 2 \uparrow^{n-1} n = \{ n,n,n-1 \} }[/math] (см. Массивная нотация Бауэрса)
[math]\displaystyle{ f_{\omega+1}(n) = \{ n,n,1,2 \} \approx G(n) }[/math] (см. Число Грэма)
[math]\displaystyle{ f_{\omega+2}(n) = \{ n,n,2,2 \} }[/math]
[math]\displaystyle{ f_{\omega+m}(n) = \{ n,n,m,2 \} }[/math]
[math]\displaystyle{ f_{\omega2}(n) = \{ n,n,n,2 \} }[/math]
[math]\displaystyle{ f_{\omega2+1}(n) = \{ n,n,1,3 \} }[/math]
[math]\displaystyle{ f_{\omega3}(n) = \{ n,n,n,3 \} }[/math]
[math]\displaystyle{ f_{\omega{m}}(n) = \{ n,n,n,m \} }[/math]
[math]\displaystyle{ f_{\omega{m+k}}(n) = \{ n,n,k,m+1 \} }[/math]
[math]\displaystyle{ f_{\omega^2}(n) = \{ n,n,n,n \} }[/math]
[math]\displaystyle{ f_{\omega^3}(n) = \{ n,n,n,n,n \} }[/math]
[math]\displaystyle{ f_{\omega^m}(n) = \{ n,n,n,...,n \} }[/math] (m раз)
[math]\displaystyle{ f_{\omega^\omega}(n) = \{ n,n,n,...,n \} }[/math] (n раз) [math]\displaystyle{ = \{ n,n (1) 2 \} }[/math]
[math]\displaystyle{ f_{\omega^{\omega+1}}(n) = \{ n,n (1) 1,2 \} }[/math]
[math]\displaystyle{ f_{\omega^{\omega+2}}(n) = \{ n,n (1) 1,1,2 \} }[/math]
[math]\displaystyle{ f_{\omega^{\omega2}}(n) = \{ n,n (1) 1 (1) 2 \} }[/math]
[math]\displaystyle{ f_{\omega^{\omega2+1}}(n) = \{ n,n (1) 1 (1) 1,2 \} }[/math]
[math]\displaystyle{ f_{\omega^{\omega3}}(n) = \{ n,n (1) 1 (1) 1 (1) 2 \} }[/math]
[math]\displaystyle{ f_{\omega^{\omega^2}}(n) = \{ n,n (2) 2 \} }[/math]
[math]\displaystyle{ f_{\omega^{\omega^3}}(n) = \{ n,n (3) 2 \} }[/math]
[math]\displaystyle{ f_{\omega^{\omega^m}}(n) = \{n,n(m)2\} }[/math]
[math]\displaystyle{ f_{\omega^{\omega^{\omega}}}(n) = \{ n,n [1,2] 2 \} }[/math] (см. Bird's Array Notation)
[math]\displaystyle{ f_{\omega^{\omega^{\omega^2}}}(n) = \{ n,n [1,1,2] 2 \} }[/math]
[math]\displaystyle{ f_{\omega^{\omega^{\omega^{\omega}}}}(n) = \{ n,n [1[2]2]2 \} }[/math]
[math]\displaystyle{ f_{\epsilon_0}(n) = \{ n,n [1{\backslash}2] 2 \} }[/math]
[math]\displaystyle{ f_{\omega^{\omega^{\epsilon_0+1}}}(n) = \{ n,n [1[1{\backslash}2]2{\backslash}2] 2 \} }[/math]
[math]\displaystyle{ f_{\omega^{\omega^{\omega^{\epsilon_0+1}}}}(n) = \{ n,n [1[1[1{\backslash}2]2{\backslash}2]2{\backslash}2] 2 \} }[/math]
[math]\displaystyle{ f_{\epsilon_1}(n) = \{ n,n [1{\backslash}3] 2 \} }[/math]
[math]\displaystyle{ f_{\epsilon_2}(n) = \{ n,n [1{\backslash}4] 2 \} }[/math]
[math]\displaystyle{ f_{\epsilon_\omega}(n) = \{ n,n [1{\backslash}1,2] 2 \} }[/math]
[math]\displaystyle{ f_{\epsilon_{\omega^{\omega}}}(n) = \{ n,n [1{\backslash}1[2]2] 2 \} }[/math]
[math]\displaystyle{ f_{\epsilon_{\epsilon_0}}(n) = \{ n,n [1{\backslash}1[1{\backslash}2]2] 2 \} }[/math]
[math]\displaystyle{ f_{\epsilon_{\epsilon_{\epsilon_0}}}(n) = \{ n,n [1{\backslash}1[1{\backslash}1[1{\backslash}2]2]2] 2 \} }[/math]
[math]\displaystyle{ f_{\zeta_0}(n) = \{ n,n [1{\backslash}1{\backslash}2] 2 \} }[/math]
[math]\displaystyle{ f_{\epsilon_{\zeta_0+1}}(n) = \{ n,n [1{\backslash}2{\backslash}2] 2 \} }[/math]

[math]\displaystyle{ f_{\epsilon_{\zeta_0+\omega}}(n) = \{ n,n [1{\backslash}1,2{\backslash}2] 2 \} }[/math]

[math]\displaystyle{ f_{\epsilon_{\zeta_0+\epsilon_0}}(n) = \{ n,n [1{\backslash}1 {[1{\backslash}2]} 2{\backslash}2] 2 \} }[/math]
[math]\displaystyle{ f_{\epsilon_{\zeta_02}}(n) = \{ n,n [1{\backslash}1 {[1{\backslash}1{\backslash}2]} 2{\backslash}2] 2 \} }[/math]
[math]\displaystyle{ f_{\epsilon_{\epsilon_{\zeta_0+1}}}(n) = \{ n,n [1{\backslash}1 {[1{\backslash}2{\backslash}2]} 2{\backslash}2] 2 \} }[/math]
[math]\displaystyle{ f_{\zeta_1}(n) = \{ n,n [1{\backslash}1{\backslash}3] 2 \} }[/math]
[math]\displaystyle{ f_{\zeta_\omega}(n) = \{ n,n [1{\backslash}1{\backslash}1,2] 2 \} }[/math]
[math]\displaystyle{ f_{\zeta_{\epsilon_0}}(n) = \{ n,n [1{\backslash}1{\backslash}1[1{\backslash}2]2] 2 \} }[/math]
[math]\displaystyle{ f_{\zeta_{\zeta_0}}(n) = \{ n,n [1{\backslash}1{\backslash}1[1{\backslash}1{\backslash}2]2] 2 \} }[/math]
[math]\displaystyle{ f_{\eta_0}(n) = \{ n,n [1{\backslash}1{\backslash}1{\backslash}2] 2 \} }[/math]
[math]\displaystyle{ f_{\varphi(4,0)}(n) = \{ n,n [1{\backslash}1{\backslash}1{\backslash}1{\backslash}2] 2 \} }[/math]
[math]\displaystyle{ f_{\varphi(m,0)}(n) = \{ n,n [1{\backslash}1{\backslash}1{\cdots}1{\backslash}2] 2 \} }[/math] (m обратных слэшей)
[math]\displaystyle{ f_{\varphi(\omega,0)}(n) = \{ n,n [1 [2{\neg}2] 2] 2\} }[/math]
[math]\displaystyle{ f_{\epsilon_{\varphi(\omega,0)+1}}(n) = \{ n,n [1{\backslash}2[2{\neg}2] 2] 2\} }[/math]
[math]\displaystyle{ f_{\zeta_{\varphi(\omega,0)+1}}(n) = \{ n,n [1{\backslash}1{\backslash}2[2{\neg}2] 2] 2\} }[/math]
[math]\displaystyle{ f_{\eta_{\varphi(\omega,0)+1}}(n) = \{ n,n [1{\backslash}1{\backslash}1{\backslash}2[2{\neg}2] 2] 2\} }[/math]
[math]\displaystyle{ f_{\varphi(\omega,1)}(n) = \{ n,n [1 [2{\neg}2] 3] 2\} }[/math]
[math]\displaystyle{ f_{\varphi(\omega,2)}(n) = \{ n,n [1 [2{\neg}2] 4] 2\} }[/math]
[math]\displaystyle{ f_{\varphi(\omega,\omega)}(n) = \{ n,n [1 [2{\neg}2] 1,2] 2\} }[/math]
[math]\displaystyle{ f_{\varphi(\omega,\epsilon_0)}(n) = \{ n,n [1 [2{\neg}2] 1[1{\backslash}2]2] 2\} }[/math]
[math]\displaystyle{ f_{\varphi(\omega,\zeta_0)}(n) = \{ n,n [1 [2{\neg}2] 1[1{\backslash}1{\backslash}2]2] 2\} }[/math]
[math]\displaystyle{ f_{\varphi(\omega,\varphi(\omega,0))}(n) = \{ n,n [1 [2{\neg}2] 1[1[2{\neg}2]2]2] 2\} }[/math]
[math]\displaystyle{ f_{\varphi(\omega,\varphi(\omega,\varphi(\omega,0)))}(n) = \{ n,n [1 [2{\neg}2] 1[1[2{\neg}2]1[1[2{\neg}2]2]2]2] 2\} }[/math]
[math]\displaystyle{ f_{\varphi(\omega+1,0)}(n) = \{ n,n [1 [2{\neg}2] 1{\backslash}2] 2\} }[/math]
[math]\displaystyle{ f_{\varphi(\omega+2,0)}(n) = \{ n,n [1 [2{\neg}2] 1{\backslash}1{\backslash}2] 2\} }[/math]
[math]\displaystyle{ f_{\varphi(\omega2,0)}(n) = \{ n,n [1 [2{\neg}2] 1 [2{\neg}2] 2] 2\} }[/math]
[math]\displaystyle{ f_{\varphi(\omega^2,0)}(n) = \{ n,n [1 [3{\neg}2] 2] 2\} }[/math]
[math]\displaystyle{ f_{\varphi(\omega^3,0)}(n) = \{ n,n [1 [4{\neg}2] 2] 2\} }[/math]
[math]\displaystyle{ f_{\varphi(\omega^{\omega},0)}(n) = \{ n,n [1 [1,2{\neg}2] 2] 2\} }[/math]
[math]\displaystyle{ f_{\varphi(\omega^{\omega^{\omega}},0)}(n) = \{ n,n [1 [1[2]2{\neg}2] 2] 2\} }[/math]
[math]\displaystyle{ f_{\varphi({\epsilon_0},0)}(n) = \{ n,n [1 [1[1{\backslash}2]2{\neg}2] 2] 2\} }[/math]
[math]\displaystyle{ f_{\Gamma_0}(n) = \{ n,n [1 [1{\backslash}2{\neg}2] 2] 2\} }[/math]
[math]\displaystyle{ f_{\Gamma_1}(n) = \{ n,n [1 [1{\backslash}2{\neg}2] 3] 2\} }[/math]
[math]\displaystyle{ f_{\Gamma_{\Gamma_0}}(n) = \{ n,n [1 [1{\backslash}2{\neg}2] 1[1[1{\backslash}2{\neg}2]2]2] 2\} }[/math]
[math]\displaystyle{ f_{\varphi(1,1,0)}(n) = \{ n,n [1 [1{\backslash}2{\neg}2]1{\backslash}2] 2\} }[/math]
[math]\displaystyle{ f_{\varphi(1,2,0)}(n) = \{ n,n [1 [1{\backslash}2{\neg}2]1{\backslash}1{\backslash}2] 2\} }[/math]
[math]\displaystyle{ f_{\varphi(2,0,0)}(n) = \{n,n[1[1{\backslash}2{\neg}2]1[1{\backslash}2{\neg}2]2]2\} }[/math]
[math]\displaystyle{ f_{\varphi(\omega,0,0)}(n) = \{ n,n [1 [2{\backslash}2{\neg}2] 2] 2\} }[/math]
[math]\displaystyle{ f_{\varphi(\Gamma_0,0,0)}(n) = \{ n,n [1[1[1[1{\backslash}2{\neg}2]2]2{\backslash}2{\neg}2]2] 2 \} }[/math]
[math]\displaystyle{ f_{\varphi(1,0,0,0)}(n) = \{ n,n [1 [1{\backslash}3{\neg}2] 2] 2\} }[/math]
[math]\displaystyle{ f_{\varphi(1,0,0,0,0)}(n) = \{ n,n [1 [1{\backslash}4{\neg}2] 2] 2\} }[/math]
[math]\displaystyle{ f_{\psi(\Omega^{\Omega^{\omega}})}(n) = \{ n,n [1 [1{\backslash}1,2{\neg}2] 2] 2\} \approx TREE(n) }[/math] (см. TREE(3))
[math]\displaystyle{ f_{\psi(\Omega^{\Omega^{\psi(\Omega^{\Omega})}})}(n) = \{ n,n [1 [1{\backslash}1[1[1{\backslash}2{\neg}2]2]2{\neg}2] 2] 2\} }[/math]
[math]\displaystyle{ f_{\psi(\Omega^{\Omega^{\Omega}})}(n) = \{ n,n [1 [1{\backslash}1{\backslash}2{\neg}2] 2] 2\} }[/math]
[math]\displaystyle{ f_{\psi(\Omega^{\Omega^{\Omega^2}})}(n) = \{ n,n [1 [1{\backslash}1{\backslash}1{\backslash}2{\neg}2] 2] 2\} }[/math]
[math]\displaystyle{ f_{\psi(\Omega^{\Omega^{\Omega^{\omega}}})}(n) = \{ n,n [1 [1[2{\neg}2]2{\neg}2] 2] 2\} }[/math]
[math]\displaystyle{ f_{\psi(\Omega^{\Omega^{\Omega^{\psi(\Omega^{\Omega^{\Omega}})}}})}(n) = \{ n,n [1 [1[1[1[1{\backslash}1{\backslash}2{\neg}2]2]2{\neg}2]2{\neg}2] 2] 2\} }[/math]
[math]\displaystyle{ f_{\psi(\Omega^{\Omega^{\Omega^{\Omega}}})}(n) = \{ n,n [1 [1[1{\backslash}2{\neg}2]2{\neg}2] 2] 2\} }[/math]
[math]\displaystyle{ f_{\psi(\Omega_2)}(n) = \{n,n [1[1{\neg}3]2] 2\} }[/math]
[math]\displaystyle{ f_{\psi(\Omega_2+1)} (n) = \{n,n [1{\backslash}2[1{\neg}3]2] 2\} }[/math]
[math]\displaystyle{ f_{\psi(\Omega_2+\omega)} (n) = \{n,n [1{\backslash}1,2[1{\neg}3]2] 2\} }[/math]
[math]\displaystyle{ f_{\psi(\Omega_2+\psi(\Omega^{\Omega}))} (n) = \{n,n [1{\backslash}1[1[1{\backslash}2{\neg}2]2]2[1{\neg}3]2] 2\} }[/math]
[math]\displaystyle{ f_{\psi(\Omega_2+\psi(\Omega^{\Omega^{\omega}}))} (n) = \{n,n [1{\backslash}1[1[1{\backslash}1,2{\neg}2]2]2[1{\neg}3]2] 2\} }[/math]
[math]\displaystyle{ f_{\psi(\Omega_2+\psi(\Omega^{\Omega^{\Omega}}))} (n) = \{n,n [1{\backslash}1[1[1{\backslash}1{\backslash}2{\neg}2]2]2[1{\neg}3]2] 2\} }[/math]
[math]\displaystyle{ f_{\psi(\Omega_2+\psi(\Omega^{\Omega^{\Omega^{\Omega}}}))} (n) = \{n,n [1{\backslash}1[1[1[1{\backslash}2{\neg}2]2{\neg}2]2]2[1{\neg}3]2] 2\} }[/math]
[math]\displaystyle{ f_{\psi(\Omega_2+\psi(\Omega_2))} (n) = \{n,n [1{\backslash}1[1[1{\neg}3]2]2[1{\neg}3]2] 2\} }[/math]
[math]\displaystyle{ f_{\psi(\Omega_2+\Omega)} (n) = \{n,n [1{\backslash}1{\backslash}2[1{\neg}3]2] 2\} }[/math]
[math]\displaystyle{ f_{\psi(\Omega_2+\Omega^2)} (n) = \{n,n [1{\backslash}1{\backslash}1{\backslash}2[1{\neg}3]2] 2\} }[/math]
[math]\displaystyle{ f_{\psi(\Omega_2+\Omega^{\omega})} (n) = \{n,n [1[2{\neg}2]2[1{\neg}3]2] 2\} }[/math]
[math]\displaystyle{ f_{\psi(\Omega_2+\Omega^{\Omega})}(n) = \{n,n [1[1{\backslash}2{\neg}2]2[1{\neg}3]2] 2\} }[/math]
[math]\displaystyle{ f_{\psi(\Omega_2+\psi_1(\Omega_2))} (n) = \{n,n [1[1{\neg}3]3] 2\} }[/math]
[math]\displaystyle{ f_{\psi(\Omega_2+\psi_1(\Omega_2+\psi_1(\Omega_2)))}(n) = \{n,n [1[1{\neg}3]1[1{\neg}3]2] 2\} }[/math]
[math]\displaystyle{ f_{\psi(\Omega_2+\psi_1(\Omega_2+\psi_1(\Omega_2+1)))}(n) = \{n,n [1[2{\neg}3]2] 2\} }[/math]
[math]\displaystyle{ f_{\psi(\Omega_2+\psi_1(\Omega_2+\psi_1(\Omega_2+\psi_1(\Omega_2))))}(n) = \{n,n [1[1[1{\neg}3]2{\neg}3]2] 2\} }[/math]
[math]\displaystyle{ f_{\psi(\Omega_22)}(n) = \{n,n [1[1{\neg}4]2] 2\} }[/math]
[math]\displaystyle{ f_{\psi(\Omega_23)}(n) = \{n,n [1[1{\neg}5]2] 2\} }[/math]
[math]\displaystyle{ f_{\psi(\Omega_2\omega)}(n) = \{n,n [1[1{\neg}1,2]2] 2\} }[/math]
[math]\displaystyle{ f_{\psi(\Omega_2\psi(0))}(n) = \{n,n [1[1{\neg}1[1{\backslash}2]2]2] 2\} }[/math]
[math]\displaystyle{ f_{\psi(\Omega_2\psi(\Omega^{\Omega}))}(n) = \{n,n [1[1{\neg}1[1[1{\backslash}2{\neg}2]2]2]2] 2\} }[/math]
[math]\displaystyle{ f_{\psi(\Omega_2\psi(\Omega_2))}(n) = \{n,n [1[1{\neg}1[1[1{\neg}3]2]2]2] 2\} }[/math]
[math]\displaystyle{ f_{\psi(\Omega_2\Omega)}(n) = \{n,n [1[1{\neg}1{\backslash}2]2] 2\} }[/math]
[math]\displaystyle{ f_{\psi(\Omega_2\Omega^{\Omega})}(n) = \{n,n [1[1{\neg}1[1{\backslash}2{\neg}2]2]2] 2\} }[/math]
[math]\displaystyle{ f_{\psi(\Omega_2\psi_1(\Omega_2))}(n) = \{n,n [1[1{\neg}1[1{\neg}3]2]2] 2\} }[/math]
[math]\displaystyle{ f_{\psi(\Omega_2^2)}(n) = \{n,n [1[1{\neg}1{\neg}2]2] 2\} }[/math]
[math]\displaystyle{ f_{\psi(\Omega_2^{\omega})}(n) = \{n,n [1[1[2{\backslash}_32]2]2] 2\} }[/math]
[math]\displaystyle{ f_{\psi(\Omega_2^{\Omega_2})}(n) = \{n,n [1[1[1{\backslash}_22{\backslash}_32]2]2] 2\} }[/math]
[math]\displaystyle{ f_{\psi(\Omega_3)}(n) = \{n,n [1[1[1{\backslash}_33]2]2] 2\} }[/math]
[math]\displaystyle{ f_{\psi(\Omega_3^{\Omega_3})}(n) = \{n,n [1[1[1[1{\backslash}_32{\backslash}_42]2]2]2] 2\} }[/math]
[math]\displaystyle{ f_{\psi(\Omega_4)}(n) = \{n,n [1[1[1[1{\backslash}_43]2]2]2] 2\} }[/math]
[math]\displaystyle{ f_{\psi(\Omega_{\omega})}(n) = \{n,n [1[2{\backslash}_{1,2}2]2] 2\} }[/math]
[math]\displaystyle{ f_{\psi(\Omega_{\psi(\Omega)})}(n) = \{n,n [1[2{\backslash}_{1[1{\backslash}2]2}2]2] 2\} }[/math]
[math]\displaystyle{ f_{\psi(\Omega_{\psi(\Omega_{\psi(\Omega)})})}(n) = \{n,n [1[2{\backslash}_{1[2{\backslash_{1[1{\backslash}2]2}}2]2}2]2] 2\} }[/math]
[math]\displaystyle{ f_{\psi(\Omega_{\Omega})}(n) = \{n,n [1[2{\backslash}_{1{\backslash}2}2]2] 2\} = (0,0,0)(1,1,1)(2,1,1)(3,1,0)[n] }[/math] (см. Bashicu Matrix System)
[math]\displaystyle{ f_{\psi({\Omega_{\Omega_2}})}(n) = (0,0,0)(1,1,1)(2,1,1)(3,1,0)(1,1,0)(2,2,1)(3,2,1)(4,2,0)[n] }[/math]
[math]\displaystyle{ f_{\psi({\Omega_{\Omega_{\omega}}})}(n) = (0,0,0)(1,1,1)(2,1,1)(3,1,0)(1,1,1)[n] }[/math]
[math]\displaystyle{ f_{\psi({\Omega_{\Omega_{\Omega}}})}(n) = (0,0,0)(1,1,1)(2,1,1)(3,1,0)(1,1,1)(2,1,1)(3,1,0)[n] }[/math]
[math]\displaystyle{ f_{\psi(\psi_I(0))}(n) = (0,0,0)(1,1,1)(2,1,1)(3,1,0)(2,0,0)[n] }[/math]

См. также

Примечания

↑ Kerr, Josh Mind blown: the fast growing hierarchy for laymen — aka enormous numbers (неопр.). Дата обращения: 7 октября 2016. Архивировано 13 июля 2019 года.

Ссылки

Buchholz, W.; Wainer, S.S (1987). "Provably Computable Functions and the Fast Growing Hierarchy". Logic and Combinatorics, edited by S. Simpson, Contemporary Mathematics, Vol. 65, AMS, 179-198.
Cichon, E. A. & Wainer, S. S. (1983), The slow-growing and the Grzegorczyk hierarchies, The Journal of Symbolic Logic Т. 48 (2): 399–408, ISSN 0022-4812, DOI 10.2307/2273557
Gallier, Jean H. (1991), What's so special about Kruskal's theorem and the ordinal Γ₀? A survey of some results in proof theory, Ann. Pure Appl. Logic Т. 53 (3): 199–260, doi:10.1016/0168-0072(91)90022-E, <http://stinet.dtic.mil/oai/oai?verb=getRecord&metadataPrefix=html&identifier=ADA290387> (недоступная ссылка) PDF's: part 1 2 3. (In particular part 3, Section 12, pp. 59–64, "A Glimpse at Hierarchies of Fast and Slow Growing Functions".)
Girard, Jean-Yves (1981), Π¹₂-logic. I. Dilators, Annals of Mathematical Logic Т. 21 (2): 75–219, ISSN 0003-4843, DOI 10.1016/0003-4843(81)90016-4
Löb, M.H.; Wainer, S.S. (1970), "Hierarchies of number theoretic functions", Arch. Math. Logik, 13. Correction, Arch. Math. Logik, 14, 1971. Part I doi:10.1007/BF01967649, Part 2 doi:10.1007/BF01973616, Corrections doi:10.1007/BF01991855.
Prömel, H. J.; Thumser, W.; Voigt, B. "Fast growing functions based on Ramsey theorems", Discrete Mathematics, v.95 n.1-3, p. 341-358, Dec. 1991 doi:10.1016/0012-365X(91)90346-4.
Wainer, S.S (1989), "Slow Growing Versus Fast Growing". Journal of Symbolic Logic 54(2): 608-614.

[1] Kerr, Josh Mind blown: the fast growing hierarchy for laymen — aka enormous numbers (неопр.). Дата обращения: 7 октября 2016. Архивировано 13 июля 2019 года.

[1]

Большие числа
Числа	Гугол Число Шеннона Гуголплекс Число Скьюза Число Мозера Число Грэма TREE(3) Число Райо
Функции	Функция Аккермана Функция Веблена Пси-функции Бухгольца Тетрация Пентация Гипероператор Быстрорастущая иерархия Медленнорастущая иерархия Иерархия Харди
Нотации	Обозначения Штейнгауза — Мозера Стрелочные обозначения Кнута Стрелочные обозначения Конвея Массивная нотация Бауэрса