Русская Википедия:Быстрорастущая иерархия

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

Определение

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

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

Фундаментальные последовательности для предельных ординалов свыше <math>\varepsilon_0</math> приведены в статьях о функциях Веблена и функциях Бухгольца.

Примеры

<math>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>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>\alpha > 1</math> верно

<math>f_{m}(n) > 2 \uparrow^{m-1} n</math>.

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

<math> 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> 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>f_{m}(10) \approx 10 \uparrow^{m-1} 11</math>.

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

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

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

	нотация Кнута	нотация Конвея	нотация Бауэрса
предел нотации	<math>\omega</math>	<math>\omega^2</math>	<math>\omega^\omega</math>
примеры	<math>f_{\omega}(10) \approx 10 \uparrow^{9} 11 =10 \uparrow \uparrow\uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \uparrow 11 </math>	<math>f_{\omega^2}(n)\approx \underbrace{n\rightarrow n \rightarrow n\cdots \rightarrow n}_{n+1 \quad \rightarrow}</math>	<math>f_{\omega^\omega}(n) \approx \underbrace{\{n,n,n, \cdots,n,n\}}_{n+2 \quad n's}</math>
	<math>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>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>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>\varepsilon_0=\omega \uparrow \uparrow n</math>. Для дальнейшего роста можно использовать функцию Веблена и другие, еще более мощные нотации для ординалов.

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

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

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

См. также

• Медленнорастущая иерархия
• Иерархия Харди

Ссылки

• 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.
• Шаблон:Citation
• Шаблон:CitationШаблон:Недоступная ссылка 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".)
• Шаблон:Citation
• 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, Part 2 Шаблон:Doi, Corrections Шаблон:Doi.
• 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.
• Wainer, S.S (1989), "Slow Growing Versus Fast Growing". Journal of Symbolic Logic 54(2): 608-614.