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

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

Определение

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

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

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

Примеры

$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$ ,

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

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

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

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

$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$ ,

$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$ ,

$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 \underbrace {n\rightarrow n\rightarrow n\cdots \rightarrow n} _{n+1\quad \rightarrow }$	$f_{\omega ^{\omega }}(n)\approx \underbrace {\{n,n,n,\cdots ,n,n\}} _{n+2\quad n's}$
примеры	$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}}$	$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}}$	$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}}$

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

Примеры

$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,...,n\}$ (m entries)
$f_{\omega ^{\omega }}(n)=\{n,n,n,...,n\}$ (n entries) $=\{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\}$ (see 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_{\epsilon _{0}}(n)=\{n,n[1{\backslash }2]2\}$
$f_{\omega ^{\omega ^{\epsilon _{0}+1}}}(n)=\{n,n[1[1{\backslash }2]2{\backslash }2]2\}$
$f_{\omega ^{\omega ^{\omega ^{\epsilon _{0}+1}}}}(n)=\{n,n[1[1[1{\backslash }2]2{\backslash }2]2{\backslash }2]2\}$
$f_{\epsilon _{1}}(n)=\{n,n[1{\backslash }3]2\}$
$f_{\epsilon _{2}}(n)=\{n,n[1{\backslash }4]2\}$
$f_{\epsilon _{\omega }}(n)=\{n,n[1{\backslash }1,2]2\}$
$f_{\epsilon _{\omega ^{\omega }}}(n)=\{n,n[1{\backslash }1[2]2]2\}$
$f_{\epsilon _{\epsilon _{0}}}(n)=\{n,n[1{\backslash }1[1{\backslash }2]2]2\}$
$f_{\epsilon _{\epsilon _{\epsilon _{0}}}}(n)=\{n,n[1{\backslash }1[1{\backslash }1[1{\backslash }2]2]2]2\}$
$f_{\zeta _{0}}(n)=\{n,n[1{\backslash }1{\backslash }2]2\}$
$f_{\epsilon _{\zeta _{0}+1}}(n)=\{n,n[1{\backslash }2{\backslash }2]2\}$

$f_{\epsilon _{\zeta _{0}+\omega }}(n)=\{n,n[1{\backslash }1,2{\backslash }2]2\}$

$f_{\epsilon _{\zeta _{0}+\epsilon _{0}}}(n)=\{n,n[1{\backslash }1{[1{\backslash }2]}2{\backslash }2]2\}$
$f_{\epsilon _{\zeta _{0}2}}(n)=\{n,n[1{\backslash }1{[1{\backslash }1{\backslash }2]}2{\backslash }2]2\}$
$f_{\epsilon _{\epsilon _{\zeta _{0}+1}}}(n)=\{n,n[1{\backslash }1{[1{\backslash }2{\backslash }2]}2{\backslash }2]2\}$
$f_{\zeta _{1}}(n)=\{n,n[1{\backslash }1{\backslash }3]2\}$
$f_{\zeta _{\omega }}(n)=\{n,n[1{\backslash }1{\backslash }1,2]2\}$
$f_{\zeta _{\epsilon _{0}}}(n)=\{n,n[1{\backslash }1{\backslash }1[1{\backslash }2]2]2\}$
$f_{\zeta _{\zeta _{0}}}(n)=\{n,n[1{\backslash }1{\backslash }1[1{\backslash }1{\backslash }2]2]2\}$
$f_{\eta _{0}}(n)=\{n,n[1{\backslash }1{\backslash }1{\backslash }2]2\}$
$f_{\varphi (4,0)}(n)=\{n,n[1{\backslash }1{\backslash }1{\backslash }1{\backslash }2]2\}$
$f_{\varphi (m,0)}(n)=\{n,n[1{\backslash }1{\backslash }1{\cdots }1{\backslash }2]2\}$ (with m backslashes)
$f_{\varphi (\omega ,0)}(n)=\{n,n[1[2{\neg }2]2]2\}$
$f_{\epsilon _{\varphi (\omega ,0)+1}}(n)=\{n,n[1{\backslash }2[2{\neg }2]2]2\}$
$f_{\zeta _{\varphi (\omega ,0)+1}}(n)=\{n,n[1{\backslash }1{\backslash }2[2{\neg }2]2]2\}$
$f_{\eta _{\varphi (\omega ,0)+1}}(n)=\{n,n[1{\backslash }1{\backslash }1{\backslash }2[2{\neg }2]2]2\}$
$f_{\varphi (\omega ,1)}(n)=\{n,n[1[2{\neg }2]3]2\}$
$f_{\varphi (\omega ,2)}(n)=\{n,n[1[2{\neg }2]4]2\}$
$f_{\varphi (\omega ,\omega )}(n)=\{n,n[1[2{\neg }2]1,2]2\}$
$f_{\varphi (\omega ,\epsilon _{0})}(n)=\{n,n[1[2{\neg }2]1[1{\backslash }2]2]2\}$
$f_{\varphi (\omega ,\zeta _{0})}(n)=\{n,n[1[2{\neg }2]1[1{\backslash }1{\backslash }2]2]2\}$
$f_{\varphi (\omega ,\varphi (\omega ,0))}(n)=\{n,n[1[2{\neg }2]1[1[2{\neg }2]2]2]2\}$
$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\}$
$f_{\varphi (\omega +1,0)}(n)=\{n,n[1[2{\neg }2]1{\backslash }2]2\}$
$f_{\varphi (\omega +2,0)}(n)=\{n,n[1[2{\neg }2]1{\backslash }1{\backslash }2]2\}$
$f_{\varphi (\omega 2,0)}(n)=\{n,n[1[2{\neg }2]1[2{\neg }2]2]2\}$
$f_{\varphi (\omega ^{2},0)}(n)=\{n,n[1[3{\neg }2]2]2\}$
$f_{\varphi (\omega ^{3},0)}(n)=\{n,n[1[4{\neg }2]2]2\}$
$f_{\varphi (\omega ^{\omega },0)}(n)=\{n,n[1[1,2{\neg }2]2]2\}$
$f_{\varphi (\omega ^{\omega ^{\omega }},0)}(n)=\{n,n[1[1[2]2{\neg }2]2]2\}$
$f_{\varphi ({\epsilon _{0}},0)}(n)=\{n,n[1[1[1{\backslash }2]2{\neg }2]2]2\}$
$f_{\Gamma _{0}}(n)=\{n,n[1[1{\backslash }2{\neg }2]2]2\}$
$f_{\Gamma _{1}}(n)=\{n,n[1[1{\backslash }2{\neg }2]3]2\}$
$f_{\Gamma _{\Gamma _{0}}}(n)=\{n,n[1[1{\backslash }2{\neg }2]1[1[1{\backslash }2{\neg }2]2]2]2\}$
$f_{\varphi (1,1,0)}(n)=\{n,n[1[1{\backslash }2{\neg }2]1{\backslash }2]2\}$
$f_{\varphi (1,2,0)}(n)=\{n,n[1[1{\backslash }2{\neg }2]1{\backslash }1{\backslash }2]2\}$
$f_{\varphi (2,0,0)}(n)=\{n,n[1[1{\backslash }2{\neg }2]1[1{\backslash }2{\neg }2]2]2\}$
$f_{\varphi (\omega ,0,0)}(n)=\{n,n[1[2{\backslash }2{\neg }2]2]2\}$
$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\}$
$f_{\varphi (1,0,0,0)}(n)=\{n,n[1[1{\backslash }3{\neg }2]2]2\}$
$f_{\varphi (1,0,0,0,0)}(n)=\{n,n[1[1{\backslash }4{\neg }2]2]2\}$
$f_{\psi (\Omega ^{\Omega ^{\omega }})}(n)=\{n,n[1[1{\backslash }1,2{\neg }2]2]2\}\approx TREE(n)$ (см. TREE(3))
$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\}$
$f_{\psi (\Omega ^{\Omega ^{\Omega }})}(n)=\{n,n[1[1{\backslash }1{\backslash }2{\neg }2]2]2\}$
$f_{\psi (\Omega ^{\Omega ^{\Omega ^{2}}})}(n)=\{n,n[1[1{\backslash }1{\backslash }1{\backslash }2{\neg }2]2]2\}$
$f_{\psi (\Omega ^{\Omega ^{\Omega ^{\omega }}})}(n)=\{n,n[1[1[2{\neg }2]2{\neg }2]2]2\}$
$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\}$
$f_{\psi (\Omega ^{\Omega ^{\Omega ^{\Omega }}})}(n)=\{n,n[1[1[1{\backslash }2{\neg }2]2{\neg }2]2]2\}$
$f_{\psi (\Omega _{2})}(n)=\{n,n[1[1{\neg }3]2]2\}$
$f_{\psi (\Omega _{2}+1)}(n)=\{n,n[1{\backslash }2[1{\neg }3]2]2\}$
$f_{\psi (\Omega _{2}+\omega )}(n)=\{n,n[1{\backslash }1,2[1{\neg }3]2]2\}$
$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\}$
$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\}$
$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\}$
$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\}$
$f_{\psi (\Omega _{2}+\psi (\Omega _{2}))}(n)=\{n,n[1{\backslash }1[1[1{\neg }3]2]2[1{\neg }3]2]2\}$
$f_{\psi (\Omega _{2}+\Omega )}(n)=\{n,n[1{\backslash }1{\backslash }2[1{\neg }3]2]2\}$
$f_{\psi (\Omega _{2}+\Omega ^{2})}(n)=\{n,n[1{\backslash }1{\backslash }1{\backslash }2[1{\neg }3]2]2\}$
$f_{\psi (\Omega _{2}+\Omega ^{\omega })}(n)=\{n,n[1[2{\neg }2]2[1{\neg }3]2]2\}$
$f_{\psi (\Omega _{2}+\Omega ^{\Omega })}(n)=\{n,n[1[1{\backslash }2{\neg }2]2[1{\neg }3]2]2\}$
$f_{\psi (\Omega _{2}+\psi _{1}(\Omega _{2}))}(n)=\{n,n[1[1{\neg }3]3]2\}$
$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\}$
$f_{\psi (\Omega _{2}+\psi _{1}(\Omega _{2}+\psi _{1}(\Omega _{2}+1)))}(n)=\{n,n[1[2{\neg }3]2]2\}$
$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\}$
$f_{\psi (\Omega _{2}2)}(n)=\{n,n[1[1{\neg }4]2]2\}$
$f_{\psi (\Omega _{2}3)}(n)=\{n,n[1[1{\neg }5]2]2\}$
$f_{\psi (\Omega _{2}\omega )}(n)=\{n,n[1[1{\neg }1,2]2]2\}$
$f_{\psi (\Omega _{2}\psi (0))}(n)=\{n,n[1[1{\neg }1[1{\backslash }2]2]2]2\}$
$f_{\psi (\Omega _{2}\psi (\Omega ^{\Omega }))}(n)=\{n,n[1[1{\neg }1[1[1{\backslash }2{\neg }2]2]2]2]2\}$
$f_{\psi (\Omega _{2}\psi (\Omega _{2}))}(n)=\{n,n[1[1{\neg }1[1[1{\neg }3]2]2]2]2\}$
$f_{\psi (\Omega _{2}\Omega )}(n)=\{n,n[1[1{\neg }1{\backslash }2]2]2\}$
$f_{\psi (\Omega _{2}\Omega ^{\Omega })}(n)=\{n,n[1[1{\neg }1[1{\backslash }2{\neg }2]2]2]2\}$
$f_{\psi (\Omega _{2}\psi _{1}(\Omega _{2}))}(n)=\{n,n[1[1{\neg }1[1{\neg }3]2]2]2\}$
$f_{\psi (\Omega _{2}^{2})}(n)=\{n,n[1[1{\neg }1{\neg }2]2]2\}$
$f_{\psi (\Omega _{2}^{\omega })}(n)=\{n,n[1[1[2{\backslash }_{3}2]2]2]2\}$
$f_{\psi (\Omega _{2}^{\Omega _{2}})}(n)=\{n,n[1[1[1{\backslash }_{2}2{\backslash }_{3}2]2]2]2\}$
$f_{\psi (\Omega _{3})}(n)=\{n,n[1[1[1{\backslash }_{3}3]2]2]2\}$
$f_{\psi (\Omega _{3}^{\Omega _{3}})}(n)=\{n,n[1[1[1[1{\backslash }_{3}2{\backslash }_{4}2]2]2]2]2\}$
$f_{\psi (\Omega _{4})}(n)=\{n,n[1[1[1[1{\backslash }_{4}3]2]2]2]2\}$
$f_{\psi (\Omega _{\omega })}(n)=\{n,n[1[2{\backslash }_{1,2}2]2]2\}$
$f_{\psi (\Omega _{\psi (\Omega )})}(n)=\{n,n[1[2{\backslash }_{1[1{\backslash }2]2}2]2]2\}$
$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\}$
$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]$ (see Bashicu Matrix System)
$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]$
$f_{\psi ({\Omega _{\Omega _{\omega }}})}(n)=(0,0,0)(1,1,1)(2,1,1)(3,1,0)(1,1,1)[n]$
$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]$
$f_{\psi (\psi _{I}(0))}(n)=(0,0,0)(1,1,1)(2,1,1)(3,1,0)(2,0,0)[n]$

См. также

Примечания

Kerr, Josh Mind blown: the fast growing hierarchy for laymen — aka enormous numbers (неопр.). Дата обращения: 7 октября 2016.

Ссылки

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.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

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