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

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

Определение

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

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

Фундаментальные последовательности для предельных ординалов свыше ${\epsilon }_0$ приведены в статьях о функциях Веблена и функциях Бухгольца.

Примеры

$f_1(n)=f_0^n(n)=\underset{n{f}_0}{\underbrace{f_0(f_0(\cdots (f_0(f_0(}}n))\cdots ))=2\times n$,

$f_2(n)=f_1^n(n)=\underset{n{f}_1}{\underbrace{f_1(f_1(\cdots (f_1(f_1(}}n))\cdots ))=2^n\times n$.

Для функций, индексированных конечными ординалами $\alpha >1$ верно

$f_m(n)>2{\uparrow }^{m-1}n$.

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

$f_3(10)=f_2^{10}(10)\approx \underset{10\text{десяток}}{\underbrace{10^{10^{10^{\cdots {}^{10^{10^{3.489}}}}}}}}\approx 10\uparrow \uparrow 11$,

$f_4(10)=f_3^{10}(10)\approx \begin{array}{ccc}& & \underbrace{10^{10^{10^{\cdots {}^{10^{10^{3.489}}}}}}}\\ & & \underbrace{10^{10^{10^{\cdots {}^{10^{10^{3.489}}}}}}}\\ & & \underbrace{⋮}\\ & & \underbrace{10^{10^{10^{\cdots {}^{10^{10^{3.489}}}}}}}\\ & & 10\text{десяток}\end{array}\}\text{10 нижних фигурных скобок}\approx 10\uparrow \uparrow \uparrow 11$,

$f_m(10)\approx 10{\uparrow }^{m-1}11$.

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

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

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

	нотация Кнута	нотация Конвея	нотация Бауэрса
предел нотации	$\omega$	${\omega }^2$	${\omega }^{\omega }$
примеры	$f_{\omega }(10)\approx 10{\uparrow }^{9}11=10\uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \uparrow 11$	$f_{{\omega }^2}(n)\approx \underset{n+1\to }{\underbrace{n\to n\to n\cdots \to n}}$	$f_{{\omega }^{\omega }}(n)\approx \underset{n+2n^{\prime }s}{\underbrace{\{n,n,n,\cdots ,n,n\}}}$
	$f_{\omega +1}(10)\approx \begin{array}{ccc}& & \underbrace{10\uparrow \uparrow \cdots \uparrow \uparrow 11}\\ & & \underbrace{10\uparrow \uparrow \cdots \uparrow \uparrow 11}\\ & & \underbrace{⋮}\\ & & \underbrace{10\uparrow \uparrow \cdots \uparrow \uparrow 11}\\ & & \text{9 стрелок}\end{array}\}\text{10}$	$f_{{\omega }^2+1}(n)\approx \begin{array}{ccc}& & \underbrace{n\to n\to \cdots n\to n}\\ & & \underbrace{n\to n\to \cdots n\to n}\\ & & \underbrace{⋮}\\ & & \underbrace{n\to n\to \cdots n\to n}\\ & & \text{n+1 стрелка}\end{array}\}\text{n}$	$f_{{\omega }^{\omega }+1}(n)\approx \begin{array}{ccc}& & \underbrace{\{n,n,n,\cdots ,n,n\}}\\ & & \underbrace{\{n,n,n,\cdots ,n,n\}}\\ & & \underbrace{⋮}\\ & & \underbrace{\{n,n,n,\cdots ,n,n\}}\\ & & \text{n+2 n's}\end{array}\}\text{n}$

Данная выше дефиниция определяет быстрорастущую иерархию до ${\epsilon }_0=\omega \uparrow \uparrow n$. Для дальнейшего роста можно использовать функцию Веблена и другие, ещё более мощные нотации для ординалов.

• $f_0(n)=n+1$
• $f_1(n)=2n$
• $f_2(n)=2^{n}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=\{n,n,n-1\}$ (см. Массивная нотация Бауэрса)
• $f_{\omega +1}(n)=\{n,n,1,2\}\approx G(n)$ (см. Число Грэма)
• $f_{\omega +2}(n)=\{n,n,2,2\}$
• $f_{\omega +m}(n)=\{n,n,m,2\}$
• $f_{\omega 2}(n)=\{n,n,n,2\}$
• $f_{\omega 2+1}(n)=\{n,n,1,3\}$
• $f_{\omega 3}(n)=\{n,n,n,3\}$
• $f_{\omega m}(n)=\{n,n,n,m\}$
• $f_{\omega m+k}(n)=\{n,n,k,m+1\}$
• $f_{{\omega }^2}(n)=\{n,n,n,n\}$
• $f_{{\omega }^3}(n)=\{n,n,n,n,n\}$
• $f_{{\omega }^m}(n)=\{n,n,n,\mathrm{...},n\}$ (m раз)
• $f_{{\omega }^{\omega }}(n)=\{n,n,n,\mathrm{...},n\}$ (n раз) $=\{n,n(1)2\}$
• $f_{{\omega }^{\omega +1}}(n)=\{n,n(1)1,2\}$
• $f_{{\omega }^{\omega +2}}(n)=\{n,n(1)1,1,2\}$
• $f_{{\omega }^{\omega 2}}(n)=\{n,n(1)1(1)2\}$
• $f_{{\omega }^{\omega 2+1}}(n)=\{n,n(1)1(1)1,2\}$
• $f_{{\omega }^{\omega 3}}(n)=\{n,n(1)1(1)1(1)2\}$
• $f_{{\omega }^{{\omega }^2}}(n)=\{n,n(2)2\}$
• $f_{{\omega }^{{\omega }^3}}(n)=\{n,n(3)2\}$
• $f_{{\omega }^{{\omega }^m}}(n)=\{n,n(m)2\}$
• $f_{{\omega }^{{\omega }^{\omega }}}(n)=\{n,n[1,2]2\}$ (см. Bird's Array Notation)
• $f_{{\omega }^{{\omega }^{{\omega }^2}}}(n)=\{n,n[1,1,2]2\}$
• $f_{{\omega }^{{\omega }^{{\omega }^{\omega }}}}(n)=\{n,n[1[2]2]2\}$
• $f_{{ϵ}_0}(n)=\{n,n[1\mathrm{\setminus }2]2\}$
• $f_{{\omega }^{{\omega }^{{ϵ}_0+1}}}(n)=\{n,n[1[1\mathrm{\setminus }2]2\mathrm{\setminus }2]2\}$
• $f_{{\omega }^{{\omega }^{{\omega }^{{ϵ}_0+1}}}}(n)=\{n,n[1[1[1\mathrm{\setminus }2]2\mathrm{\setminus }2]2\mathrm{\setminus }2]2\}$
• $f_{{ϵ}_1}(n)=\{n,n[1\mathrm{\setminus }3]2\}$
• $f_{{ϵ}_2}(n)=\{n,n[1\mathrm{\setminus }4]2\}$
• $f_{{ϵ}_{\omega }}(n)=\{n,n[1\mathrm{\setminus }1,2]2\}$
• $f_{{ϵ}_{{\omega }^{\omega }}}(n)=\{n,n[1\mathrm{\setminus }1[2]2]2\}$
• $f_{{ϵ}_{{ϵ}_0}}(n)=\{n,n[1\mathrm{\setminus }1[1\mathrm{\setminus }2]2]2\}$
• $f_{{ϵ}_{{ϵ}_{{ϵ}_0}}}(n)=\{n,n[1\mathrm{\setminus }1[1\mathrm{\setminus }1[1\mathrm{\setminus }2]2]2]2\}$
• $f_{{\zeta }_0}(n)=\{n,n[1\mathrm{\setminus }1\mathrm{\setminus }2]2\}$
• $f_{{ϵ}_{{\zeta }_0+1}}(n)=\{n,n[1\mathrm{\setminus }2\mathrm{\setminus }2]2\}$
• $f_{{ϵ}_{{\zeta }_0+\omega }}(n)=\{n,n[1\mathrm{\setminus }1,2\mathrm{\setminus }2]2\}$
• $f_{{ϵ}_{{\zeta }_0+{ϵ}_0}}(n)=\{n,n[1\mathrm{\setminus }1[1\mathrm{\setminus }2]2\mathrm{\setminus }2]2\}$
• $f_{{ϵ}_{{\zeta }_{0}2}}(n)=\{n,n[1\mathrm{\setminus }1[1\mathrm{\setminus }1\mathrm{\setminus }2]2\mathrm{\setminus }2]2\}$
• $f_{{ϵ}_{{ϵ}_{{\zeta }_0+1}}}(n)=\{n,n[1\mathrm{\setminus }1[1\mathrm{\setminus }2\mathrm{\setminus }2]2\mathrm{\setminus }2]2\}$
• $f_{{\zeta }_1}(n)=\{n,n[1\mathrm{\setminus }1\mathrm{\setminus }3]2\}$
• $f_{{\zeta }_{\omega }}(n)=\{n,n[1\mathrm{\setminus }1\mathrm{\setminus }1,2]2\}$
• $f_{{\zeta }_{{ϵ}_0}}(n)=\{n,n[1\mathrm{\setminus }1\mathrm{\setminus }1[1\mathrm{\setminus }2]2]2\}$
• $f_{{\zeta }_{{\zeta }_0}}(n)=\{n,n[1\mathrm{\setminus }1\mathrm{\setminus }1[1\mathrm{\setminus }1\mathrm{\setminus }2]2]2\}$
• $f_{{\eta }_0}(n)=\{n,n[1\mathrm{\setminus }1\mathrm{\setminus }1\mathrm{\setminus }2]2\}$
• $f_{\phi (4,0)}(n)=\{n,n[1\mathrm{\setminus }1\mathrm{\setminus }1\mathrm{\setminus }1\mathrm{\setminus }2]2\}$
• $f_{\phi (m,0)}(n)=\{n,n[1\mathrm{\setminus }1\mathrm{\setminus }1\cdots 1\mathrm{\setminus }2]2\}$ (m обратных слэшей)
• $f_{\phi (\omega ,0)}(n)=\{n,n[1[2\mathrm{\neg }2]2]2\}$
• $f_{{ϵ}_{\phi (\omega ,0)+1}}(n)=\{n,n[1\mathrm{\setminus }2[2\mathrm{\neg }2]2]2\}$
• $f_{{\zeta }_{\phi (\omega ,0)+1}}(n)=\{n,n[1\mathrm{\setminus }1\mathrm{\setminus }2[2\mathrm{\neg }2]2]2\}$
• $f_{{\eta }_{\phi (\omega ,0)+1}}(n)=\{n,n[1\mathrm{\setminus }1\mathrm{\setminus }1\mathrm{\setminus }2[2\mathrm{\neg }2]2]2\}$
• $f_{\phi (\omega ,1)}(n)=\{n,n[1[2\mathrm{\neg }2]3]2\}$
• $f_{\phi (\omega ,2)}(n)=\{n,n[1[2\mathrm{\neg }2]4]2\}$
• $f_{\phi (\omega ,\omega )}(n)=\{n,n[1[2\mathrm{\neg }2]1,2]2\}$
• $f_{\phi (\omega ,{ϵ}_0)}(n)=\{n,n[1[2\mathrm{\neg }2]1[1\mathrm{\setminus }2]2]2\}$
• $f_{\phi (\omega ,{\zeta }_0)}(n)=\{n,n[1[2\mathrm{\neg }2]1[1\mathrm{\setminus }1\mathrm{\setminus }2]2]2\}$
• $f_{\phi (\omega ,\phi (\omega ,0))}(n)=\{n,n[1[2\mathrm{\neg }2]1[1[2\mathrm{\neg }2]2]2]2\}$
• $f_{\phi (\omega ,\phi (\omega ,\phi (\omega ,0)))}(n)=\{n,n[1[2\mathrm{\neg }2]1[1[2\mathrm{\neg }2]1[1[2\mathrm{\neg }2]2]2]2]2\}$
• $f_{\phi (\omega +1,0)}(n)=\{n,n[1[2\mathrm{\neg }2]1\mathrm{\setminus }2]2\}$
• $f_{\phi (\omega +2,0)}(n)=\{n,n[1[2\mathrm{\neg }2]1\mathrm{\setminus }1\mathrm{\setminus }2]2\}$
• $f_{\phi (\omega 2,0)}(n)=\{n,n[1[2\mathrm{\neg }2]1[2\mathrm{\neg }2]2]2\}$
• $f_{\phi ({\omega }^2,0)}(n)=\{n,n[1[3\mathrm{\neg }2]2]2\}$
• $f_{\phi ({\omega }^3,0)}(n)=\{n,n[1[4\mathrm{\neg }2]2]2\}$
• $f_{\phi ({\omega }^{\omega },0)}(n)=\{n,n[1[1,2\mathrm{\neg }2]2]2\}$
• $f_{\phi ({\omega }^{{\omega }^{\omega }},0)}(n)=\{n,n[1[1[2]2\mathrm{\neg }2]2]2\}$
• $f_{\phi ({ϵ}_0,0)}(n)=\{n,n[1[1[1\mathrm{\setminus }2]2\mathrm{\neg }2]2]2\}$
• $f_{{\mathrm{\Gamma }}_0}(n)=\{n,n[1[1\mathrm{\setminus }2\mathrm{\neg }2]2]2\}$
• $f_{{\mathrm{\Gamma }}_1}(n)=\{n,n[1[1\mathrm{\setminus }2\mathrm{\neg }2]3]2\}$
• $f_{{\mathrm{\Gamma }}_{{\mathrm{\Gamma }}_0}}(n)=\{n,n[1[1\mathrm{\setminus }2\mathrm{\neg }2]1[1[1\mathrm{\setminus }2\mathrm{\neg }2]2]2]2\}$
• $f_{\phi (1,1,0)}(n)=\{n,n[1[1\mathrm{\setminus }2\mathrm{\neg }2]1\mathrm{\setminus }2]2\}$
• $f_{\phi (1,2,0)}(n)=\{n,n[1[1\mathrm{\setminus }2\mathrm{\neg }2]1\mathrm{\setminus }1\mathrm{\setminus }2]2\}$
• $f_{\phi (2,0,0)}(n)=\{n,n[1[1\mathrm{\setminus }2\mathrm{\neg }2]1[1\mathrm{\setminus }2\mathrm{\neg }2]2]2\}$
• $f_{\phi (\omega ,0,0)}(n)=\{n,n[1[2\mathrm{\setminus }2\mathrm{\neg }2]2]2\}$
• $f_{\phi ({\mathrm{\Gamma }}_0,0,0)}(n)=\{n,n[1[1[1[1\mathrm{\setminus }2\mathrm{\neg }2]2]2\mathrm{\setminus }2\mathrm{\neg }2]2]2\}$
• $f_{\phi (1,0,0,0)}(n)=\{n,n[1[1\mathrm{\setminus }3\mathrm{\neg }2]2]2\}$
• $f_{\phi (1,0,0,0,0)}(n)=\{n,n[1[1\mathrm{\setminus }4\mathrm{\neg }2]2]2\}$
• $f_{\psi ({\mathrm{\Omega }}^{{\mathrm{\Omega }}^{\omega }})}(n)=\{n,n[1[1\mathrm{\setminus }1,2\mathrm{\neg }2]2]2\}\approx TREE(n)$ (см. TREE(3))
• $f_{\psi ({\mathrm{\Omega }}^{{\mathrm{\Omega }}^{\psi ({\mathrm{\Omega }}^{\mathrm{\Omega }})}})}(n)=\{n,n[1[1\mathrm{\setminus }1[1[1\mathrm{\setminus }2\mathrm{\neg }2]2]2\mathrm{\neg }2]2]2\}$
• $f_{\psi ({\mathrm{\Omega }}^{{\mathrm{\Omega }}^{\mathrm{\Omega }}})}(n)=\{n,n[1[1\mathrm{\setminus }1\mathrm{\setminus }2\mathrm{\neg }2]2]2\}$
• $f_{\psi ({\mathrm{\Omega }}^{{\mathrm{\Omega }}^{{\mathrm{\Omega }}^2}})}(n)=\{n,n[1[1\mathrm{\setminus }1\mathrm{\setminus }1\mathrm{\setminus }2\mathrm{\neg }2]2]2\}$
• $f_{\psi ({\mathrm{\Omega }}^{{\mathrm{\Omega }}^{{\mathrm{\Omega }}^{\omega }}})}(n)=\{n,n[1[1[2\mathrm{\neg }2]2\mathrm{\neg }2]2]2\}$
• $f_{\psi ({\mathrm{\Omega }}^{{\mathrm{\Omega }}^{{\mathrm{\Omega }}^{\psi ({\mathrm{\Omega }}^{{\mathrm{\Omega }}^{\mathrm{\Omega }}})}}})}(n)=\{n,n[1[1[1[1[1\mathrm{\setminus }1\mathrm{\setminus }2\mathrm{\neg }2]2]2\mathrm{\neg }2]2\mathrm{\neg }2]2]2\}$
• $f_{\psi ({\mathrm{\Omega }}^{{\mathrm{\Omega }}^{{\mathrm{\Omega }}^{\mathrm{\Omega }}}})}(n)=\{n,n[1[1[1\mathrm{\setminus }2\mathrm{\neg }2]2\mathrm{\neg }2]2]2\}$
• $f_{\psi ({\mathrm{\Omega }}_2)}(n)=\{n,n[1[1\mathrm{\neg }3]2]2\}$
• $f_{\psi ({\mathrm{\Omega }}_2+1)}(n)=\{n,n[1\mathrm{\setminus }2[1\mathrm{\neg }3]2]2\}$
• $f_{\psi ({\mathrm{\Omega }}_2+\omega )}(n)=\{n,n[1\mathrm{\setminus }1,2[1\mathrm{\neg }3]2]2\}$
• $f_{\psi ({\mathrm{\Omega }}_2+\psi ({\mathrm{\Omega }}^{\mathrm{\Omega }}))}(n)=\{n,n[1\mathrm{\setminus }1[1[1\mathrm{\setminus }2\mathrm{\neg }2]2]2[1\mathrm{\neg }3]2]2\}$
• $f_{\psi ({\mathrm{\Omega }}_2+\psi ({\mathrm{\Omega }}^{{\mathrm{\Omega }}^{\omega }}))}(n)=\{n,n[1\mathrm{\setminus }1[1[1\mathrm{\setminus }1,2\mathrm{\neg }2]2]2[1\mathrm{\neg }3]2]2\}$
• $f_{\psi ({\mathrm{\Omega }}_2+\psi ({\mathrm{\Omega }}^{{\mathrm{\Omega }}^{\mathrm{\Omega }}}))}(n)=\{n,n[1\mathrm{\setminus }1[1[1\mathrm{\setminus }1\mathrm{\setminus }2\mathrm{\neg }2]2]2[1\mathrm{\neg }3]2]2\}$
• $f_{\psi ({\mathrm{\Omega }}_2+\psi ({\mathrm{\Omega }}^{{\mathrm{\Omega }}^{{\mathrm{\Omega }}^{\mathrm{\Omega }}}}))}(n)=\{n,n[1\mathrm{\setminus }1[1[1[1\mathrm{\setminus }2\mathrm{\neg }2]2\mathrm{\neg }2]2]2[1\mathrm{\neg }3]2]2\}$
• $f_{\psi ({\mathrm{\Omega }}_2+\psi ({\mathrm{\Omega }}_2))}(n)=\{n,n[1\mathrm{\setminus }1[1[1\mathrm{\neg }3]2]2[1\mathrm{\neg }3]2]2\}$
• $f_{\psi ({\mathrm{\Omega }}_2+\mathrm{\Omega })}(n)=\{n,n[1\mathrm{\setminus }1\mathrm{\setminus }2[1\mathrm{\neg }3]2]2\}$
• $f_{\psi ({\mathrm{\Omega }}_2+{\mathrm{\Omega }}^2)}(n)=\{n,n[1\mathrm{\setminus }1\mathrm{\setminus }1\mathrm{\setminus }2[1\mathrm{\neg }3]2]2\}$
• $f_{\psi ({\mathrm{\Omega }}_2+{\mathrm{\Omega }}^{\omega })}(n)=\{n,n[1[2\mathrm{\neg }2]2[1\mathrm{\neg }3]2]2\}$
• $f_{\psi ({\mathrm{\Omega }}_2+{\mathrm{\Omega }}^{\mathrm{\Omega }})}(n)=\{n,n[1[1\mathrm{\setminus }2\mathrm{\neg }2]2[1\mathrm{\neg }3]2]2\}$
• $f_{\psi ({\mathrm{\Omega }}_2+{\psi }_1({\mathrm{\Omega }}_2))}(n)=\{n,n[1[1\mathrm{\neg }3]3]2\}$
• $f_{\psi ({\mathrm{\Omega }}_2+{\psi }_1({\mathrm{\Omega }}_2+{\psi }_1({\mathrm{\Omega }}_2)))}(n)=\{n,n[1[1\mathrm{\neg }3]1[1\mathrm{\neg }3]2]2\}$
• $f_{\psi ({\mathrm{\Omega }}_2+{\psi }_1({\mathrm{\Omega }}_2+{\psi }_1({\mathrm{\Omega }}_2+1)))}(n)=\{n,n[1[2\mathrm{\neg }3]2]2\}$
• $f_{\psi ({\mathrm{\Omega }}_2+{\psi }_1({\mathrm{\Omega }}_2+{\psi }_1({\mathrm{\Omega }}_2+{\psi }_1({\mathrm{\Omega }}_2))))}(n)=\{n,n[1[1[1\mathrm{\neg }3]2\mathrm{\neg }3]2]2\}$
• $f_{\psi ({\mathrm{\Omega }}_{2}2)}(n)=\{n,n[1[1\mathrm{\neg }4]2]2\}$
• $f_{\psi ({\mathrm{\Omega }}_{2}3)}(n)=\{n,n[1[1\mathrm{\neg }5]2]2\}$
• $f_{\psi ({\mathrm{\Omega }}_2\omega )}(n)=\{n,n[1[1\mathrm{\neg }1,2]2]2\}$
• $f_{\psi ({\mathrm{\Omega }}_2\psi (0))}(n)=\{n,n[1[1\mathrm{\neg }1[1\mathrm{\setminus }2]2]2]2\}$
• $f_{\psi ({\mathrm{\Omega }}_2\psi ({\mathrm{\Omega }}^{\mathrm{\Omega }}))}(n)=\{n,n[1[1\mathrm{\neg }1[1[1\mathrm{\setminus }2\mathrm{\neg }2]2]2]2]2\}$
• $f_{\psi ({\mathrm{\Omega }}_2\psi ({\mathrm{\Omega }}_2))}(n)=\{n,n[1[1\mathrm{\neg }1[1[1\mathrm{\neg }3]2]2]2]2\}$
• $f_{\psi ({\mathrm{\Omega }}_2\mathrm{\Omega })}(n)=\{n,n[1[1\mathrm{\neg }1\mathrm{\setminus }2]2]2\}$
• $f_{\psi ({\mathrm{\Omega }}_2{\mathrm{\Omega }}^{\mathrm{\Omega }})}(n)=\{n,n[1[1\mathrm{\neg }1[1\mathrm{\setminus }2\mathrm{\neg }2]2]2]2\}$
• $f_{\psi ({\mathrm{\Omega }}_2{\psi }_1({\mathrm{\Omega }}_2))}(n)=\{n,n[1[1\mathrm{\neg }1[1\mathrm{\neg }3]2]2]2\}$
• $f_{\psi ({\mathrm{\Omega }}_2^2)}(n)=\{n,n[1[1\mathrm{\neg }1\mathrm{\neg }2]2]2\}$
• $f_{\psi ({\mathrm{\Omega }}_2^{\omega })}(n)=\{n,n[1[1[2{\mathrm{\setminus }}_{3}2]2]2]2\}$
• $f_{\psi ({\mathrm{\Omega }}_2^{{\mathrm{\Omega }}_2})}(n)=\{n,n[1[1[1{\mathrm{\setminus }}_{2}2{\mathrm{\setminus }}_{3}2]2]2]2\}$
• $f_{\psi ({\mathrm{\Omega }}_3)}(n)=\{n,n[1[1[1{\mathrm{\setminus }}_{3}3]2]2]2\}$
• $f_{\psi ({\mathrm{\Omega }}_3^{{\mathrm{\Omega }}_3})}(n)=\{n,n[1[1[1[1{\mathrm{\setminus }}_{3}2{\mathrm{\setminus }}_{4}2]2]2]2]2\}$
• $f_{\psi ({\mathrm{\Omega }}_4)}(n)=\{n,n[1[1[1[1{\mathrm{\setminus }}_{4}3]2]2]2]2\}$
• $f_{\psi ({\mathrm{\Omega }}_{\omega })}(n)=\{n,n[1[2{\mathrm{\setminus }}_{1,2}2]2]2\}$
• $f_{\psi ({\mathrm{\Omega }}_{\psi (\mathrm{\Omega })})}(n)=\{n,n[1[2{\mathrm{\setminus }}_{1[1\mathrm{\setminus }2]2}2]2]2\}$
• $f_{\psi ({\mathrm{\Omega }}_{\psi ({\mathrm{\Omega }}_{\psi (\mathrm{\Omega })})})}(n)=\{n,n[1[2{\mathrm{\setminus }}_{1[2{\mathrm{\setminus }}_{1[1\mathrm{\setminus }2]2}2]2}2]2]2\}$
• $f_{\psi ({\mathrm{\Omega }}_{\mathrm{\Omega }})}(n)=\{n,n[1[2{\mathrm{\setminus }}_{1\mathrm{\setminus }2}2]2]2\}=(0,0,0)(1,1,1)(2,1,1)(3,1,0)[n]$ (см. Bashicu Matrix System)
• $f_{\psi ({\mathrm{\Omega }}_{{\mathrm{\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]$
• $f_{\psi ({\mathrm{\Omega }}_{{\mathrm{\Omega }}_{\omega }})}(n)=(0,0,0)(1,1,1)(2,1,1)(3,1,0)(1,1,1)[n]$
• $f_{\psi ({\mathrm{\Omega }}_{{\mathrm{\Omega }}_{\mathrm{\Omega }}})}(n)=(0,0,0)(1,1,1)(2,1,1)(3,1,0)(1,1,1)(2,1,1)(3,1,0)[n]$
• $f_{\psi ({\psi }_I(0))}(n)=(0,0,0)(1,1,1)(2,1,1)(3,1,0)(2,0,0)[n]$

См. также

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

Ссылки

• 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.