Быстрорастущая иерархия (также называемая расширенной иерархией Гржегорчика ) — это семейство быстрорастущих функций, индексированных ординалами . Наиболее известным частным случаем быстрорастущей иерархии является иерархия Лёба -Вайнера.
Быстрорастущая иерархия определяется следующими правилами:
f 0 ( n ) = n + 1 {\displaystyle f_{0}(n)=n+1} (в общем случае f 0 ( n ) {\displaystyle f_{0}(n)} может быть любой растущей функцией), f α + 1 ( n ) = f α n ( n ) = f α ( f α ( ⋯ ( f α ( f α ( ⏟ n раз n ) ) ⋯ ) ) {\displaystyle f_{\alpha +1}(n)=f_{\alpha }^{n}(n)=\underbrace {f_{\alpha }(f_{\alpha }(\cdots (f_{\alpha }(f_{\alpha }(} _{n{\mbox{ раз}}}n))\cdots ))} , f α ( n ) = f α [ n ] ( n ) {\displaystyle f_{\alpha }(n)=f_{\alpha [n]}(n)} если α {\displaystyle \alpha } предельный ординал, где α [ n ] {\displaystyle \alpha [n]} является n -м элементом фундаментальной последовательности, установленной для некого предельного ординала α {\displaystyle \alpha } . Существуют различные версии быстрорастущей иерархии, однако наиболее известной является иерархия Лёба-Вайнера, в которой фундаментальные последовательности для предельных ординалов, записанных в нормальной форме Кантора, определяются следующими правилами: ω [ n ] = n {\displaystyle \omega [n]=n} , ( ω α 1 + ω α 2 + ⋯ + ω α k − 1 + ω α k ) [ n ] = ω α 1 + ω α 2 + ⋯ + ω α k − 1 + ω α k [ n ] {\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]} для α 1 ≥ α 2 ≥ ⋯ ≥ α k {\displaystyle \alpha _{1}\geq \alpha _{2}\geq \cdots \geq \alpha _{k}} , ω α + 1 [ n ] = ω α n {\displaystyle \omega ^{\alpha +1}[n]=\omega ^{\alpha }n} , ω α [ n ] = ω α [ n ] {\displaystyle \omega ^{\alpha }[n]=\omega ^{\alpha [n]}} если α {\displaystyle \alpha } предельный ординал, ε 0 [ 0 ] = 0 {\displaystyle \varepsilon _{0}[0]=0} и ε 0 [ n + 1 ] = ω ε 0 [ n ] = ω ↑↑ n {\displaystyle \varepsilon _{0}[n+1]=\omega ^{\varepsilon _{0}[n]}=\omega \uparrow \uparrow n} . Фундаментальные последовательности для предельных ординалов свыше ε 0 {\displaystyle \varepsilon _{0}} приведены в статьях о функциях Веблена и функциях Бухгольца .
f 1 ( n ) = f 0 n ( n ) = f 0 ( f 0 ( ⋯ ( f 0 ( f 0 ( ⏟ n f 0 n ) ) ⋯ ) ) = 2 × n {\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} ,
f 2 ( n ) = f 1 n ( n ) = f 1 ( f 1 ( ⋯ ( f 1 ( f 1 ( ⏟ n f 1 n ) ) ⋯ ) ) = 2 n × n {\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} .
Для функций, индексированных конечными ординалами α > 1 {\displaystyle \alpha >1} верно
f m ( n ) > 2 ↑ m − 1 n {\displaystyle f_{m}(n)>2\uparrow ^{m-1}n} .
В частности, при n =10:
f 3 ( 10 ) = f 2 10 ( 10 ) ≈ 10 10 10 ⋯ 10 10 3.489 ⏟ 10 десяток ≈ 10 ↑↑ 11 {\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} ,
f 4 ( 10 ) = f 3 10 ( 10 ) ≈ 10 10 10 ⋯ 10 10 3.489 ⏟ 10 10 10 ⋯ 10 10 3.489 ⏟ ⋮ ⏟ 10 10 10 ⋯ 10 10 3.489 ⏟ 10 десяток } 10 нижних фигурных скобок ≈ 10 ↑↑↑ 11 {\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} ,
f m ( 10 ) ≈ 10 ↑ m − 1 11 {\displaystyle f_{m}(10)\approx 10\uparrow ^{m-1}11} .
Таким образом, уже первый трансфинитный ординал ω {\displaystyle \omega } соответствует пределу стрелочной нотации Кнута .
Знаменитое число Грэма меньше, чем f ω + 1 ( 64 ) {\displaystyle f_{\omega +1}(64)} .
Благодаря простоте и ясности определения быстрорастущая иерархия применяется для анализа различных нотаций для записи больших чисел .
нотация Кнута нотация Конвея нотация Бауэрса предел нотации ω {\displaystyle \omega } ω 2 {\displaystyle \omega ^{2}} ω ω {\displaystyle \omega ^{\omega }} примеры f ω ( 10 ) ≈ 10 ↑ 9 11 = 10 ↑↑↑↑↑↑↑↑↑ 11 {\displaystyle f_{\omega }(10)\approx 10\uparrow ^{9}11=10\uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \uparrow 11} f ω 2 ( n ) ≈ n → n → n ⋯ → n ⏟ n + 1 → {\displaystyle f_{\omega ^{2}}(n)\approx \underbrace {n\rightarrow n\rightarrow n\cdots \rightarrow n} _{n+1\quad \rightarrow }} f ω ω ( n ) ≈ { n , n , n , ⋯ , n , n } ⏟ n + 2 n ′ s {\displaystyle f_{\omega ^{\omega }}(n)\approx \underbrace {\{n,n,n,\cdots ,n,n\}} _{n+2\quad n's}} f ω + 1 ( 10 ) ≈ 10 ↑↑ ⋯ ↑↑ 11 ⏟ 10 ↑↑ ⋯ ↑↑ 11 ⏟ ⋮ ⏟ 10 ↑↑ ⋯ ↑↑ 11 ⏟ 9 стрелок } 10 {\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}}} f ω 2 + 1 ( n ) ≈ n → n → ⋯ n → n ⏟ n → n → ⋯ n → n ⏟ ⋮ ⏟ n → n → ⋯ n → n ⏟ n+1 стрелка } n {\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}}} f ω ω + 1 ( n ) ≈ { n , n , n , ⋯ , n , n } ⏟ { n , n , n , ⋯ , n , n } ⏟ ⋮ ⏟ { n , n , n , ⋯ , n , n } ⏟ n+2 n's } n {\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}}}
Данная выше дефиниция определяет быстрорастущую иерархию до ε 0 = ω ↑↑ n {\displaystyle \varepsilon _{0}=\omega \uparrow \uparrow n} . Для дальнейшего роста можно использовать функцию Веблена и другие, ещё более мощные нотации для ординалов[1] .
f 0 ( n ) = n + 1 {\displaystyle f_{0}(n)=n+1} f 1 ( n ) = 2 n {\displaystyle f_{1}(n)=2n} f 2 ( n ) = 2 n n {\displaystyle f_{2}(n)=2^{n}n} f 3 ( n ) > 2 ↑↑ n {\displaystyle f_{3}(n)>2\uparrow \uparrow n} (см. Стрелочная нотация Кнута ) f 4 ( n ) > 2 ↑↑↑ n {\displaystyle f_{4}(n)>2\uparrow \uparrow \uparrow n} f m ( n ) > 2 ↑ m − 1 n {\displaystyle f_{m}(n)>2\uparrow ^{m-1}n} f ω ( n ) > 2 ↑ n − 1 n = { n , n , n − 1 } {\displaystyle f_{\omega }(n)>2\uparrow ^{n-1}n=\{n,n,n-1\}} (см. Массивная нотация Бауэрса ) f ω + 1 ( n ) = { n , n , 1 , 2 } ≈ G ( n ) {\displaystyle f_{\omega +1}(n)=\{n,n,1,2\}\approx G(n)} (см. Число Грэма ) f ω + 2 ( n ) = { n , n , 2 , 2 } {\displaystyle f_{\omega +2}(n)=\{n,n,2,2\}} f ω + m ( n ) = { n , n , m , 2 } {\displaystyle f_{\omega +m}(n)=\{n,n,m,2\}} f ω 2 ( n ) = { n , n , n , 2 } {\displaystyle f_{\omega 2}(n)=\{n,n,n,2\}} f ω 2 + 1 ( n ) = { n , n , 1 , 3 } {\displaystyle f_{\omega 2+1}(n)=\{n,n,1,3\}} f ω 3 ( n ) = { n , n , n , 3 } {\displaystyle f_{\omega 3}(n)=\{n,n,n,3\}} f ω m ( n ) = { n , n , n , m } {\displaystyle f_{\omega {m}}(n)=\{n,n,n,m\}} f ω m + k ( n ) = { n , n , k , m + 1 } {\displaystyle f_{\omega {m+k}}(n)=\{n,n,k,m+1\}} f ω 2 ( n ) = { n , n , n , n } {\displaystyle f_{\omega ^{2}}(n)=\{n,n,n,n\}} f ω 3 ( n ) = { n , n , n , n , n } {\displaystyle f_{\omega ^{3}}(n)=\{n,n,n,n,n\}} f ω m ( n ) = { n , n , n , . . . , n } {\displaystyle f_{\omega ^{m}}(n)=\{n,n,n,...,n\}} (m раз) f ω ω ( n ) = { n , n , n , . . . , n } {\displaystyle f_{\omega ^{\omega }}(n)=\{n,n,n,...,n\}} (n раз) = { n , n ( 1 ) 2 } {\displaystyle =\{n,n(1)2\}} f ω ω + 1 ( n ) = { n , n ( 1 ) 1 , 2 } {\displaystyle f_{\omega ^{\omega +1}}(n)=\{n,n(1)1,2\}} f ω ω + 2 ( n ) = { n , n ( 1 ) 1 , 1 , 2 } {\displaystyle f_{\omega ^{\omega +2}}(n)=\{n,n(1)1,1,2\}} f ω ω 2 ( n ) = { n , n ( 1 ) 1 ( 1 ) 2 } {\displaystyle f_{\omega ^{\omega 2}}(n)=\{n,n(1)1(1)2\}} f ω ω 2 + 1 ( n ) = { n , n ( 1 ) 1 ( 1 ) 1 , 2 } {\displaystyle f_{\omega ^{\omega 2+1}}(n)=\{n,n(1)1(1)1,2\}} f ω ω 3 ( n ) = { n , n ( 1 ) 1 ( 1 ) 1 ( 1 ) 2 } {\displaystyle f_{\omega ^{\omega 3}}(n)=\{n,n(1)1(1)1(1)2\}} f ω ω 2 ( n ) = { n , n ( 2 ) 2 } {\displaystyle f_{\omega ^{\omega ^{2}}}(n)=\{n,n(2)2\}} f ω ω 3 ( n ) = { n , n ( 3 ) 2 } {\displaystyle f_{\omega ^{\omega ^{3}}}(n)=\{n,n(3)2\}} f ω ω m ( n ) = { n , n ( m ) 2 } {\displaystyle f_{\omega ^{\omega ^{m}}}(n)=\{n,n(m)2\}} f ω ω ω ( n ) = { n , n [ 1 , 2 ] 2 } {\displaystyle f_{\omega ^{\omega ^{\omega }}}(n)=\{n,n[1,2]2\}} (см. Bird's Array Notation ) f ω ω ω 2 ( n ) = { n , n [ 1 , 1 , 2 ] 2 } {\displaystyle f_{\omega ^{\omega ^{\omega ^{2}}}}(n)=\{n,n[1,1,2]2\}} f ω ω ω ω ( n ) = { n , n [ 1 [ 2 ] 2 ] 2 } {\displaystyle f_{\omega ^{\omega ^{\omega ^{\omega }}}}(n)=\{n,n[1[2]2]2\}} f ϵ 0 ( n ) = { n , n [ 1 ∖ 2 ] 2 } {\displaystyle f_{\epsilon _{0}}(n)=\{n,n[1{\backslash }2]2\}} f ω ω ϵ 0 + 1 ( n ) = { n , n [ 1 [ 1 ∖ 2 ] 2 ∖ 2 ] 2 } {\displaystyle f_{\omega ^{\omega ^{\epsilon _{0}+1}}}(n)=\{n,n[1[1{\backslash }2]2{\backslash }2]2\}} f ω ω ω ϵ 0 + 1 ( n ) = { n , n [ 1 [ 1 [ 1 ∖ 2 ] 2 ∖ 2 ] 2 ∖ 2 ] 2 } {\displaystyle f_{\omega ^{\omega ^{\omega ^{\epsilon _{0}+1}}}}(n)=\{n,n[1[1[1{\backslash }2]2{\backslash }2]2{\backslash }2]2\}} f ϵ 1 ( n ) = { n , n [ 1 ∖ 3 ] 2 } {\displaystyle f_{\epsilon _{1}}(n)=\{n,n[1{\backslash }3]2\}} f ϵ 2 ( n ) = { n , n [ 1 ∖ 4 ] 2 } {\displaystyle f_{\epsilon _{2}}(n)=\{n,n[1{\backslash }4]2\}} f ϵ ω ( n ) = { n , n [ 1 ∖ 1 , 2 ] 2 } {\displaystyle f_{\epsilon _{\omega }}(n)=\{n,n[1{\backslash }1,2]2\}} f ϵ ω ω ( n ) = { n , n [ 1 ∖ 1 [ 2 ] 2 ] 2 } {\displaystyle f_{\epsilon _{\omega ^{\omega }}}(n)=\{n,n[1{\backslash }1[2]2]2\}} f ϵ ϵ 0 ( n ) = { n , n [ 1 ∖ 1 [ 1 ∖ 2 ] 2 ] 2 } {\displaystyle f_{\epsilon _{\epsilon _{0}}}(n)=\{n,n[1{\backslash }1[1{\backslash }2]2]2\}} f ϵ ϵ ϵ 0 ( n ) = { n , n [ 1 ∖ 1 [ 1 ∖ 1 [ 1 ∖ 2 ] 2 ] 2 ] 2 } {\displaystyle f_{\epsilon _{\epsilon _{\epsilon _{0}}}}(n)=\{n,n[1{\backslash }1[1{\backslash }1[1{\backslash }2]2]2]2\}} f ζ 0 ( n ) = { n , n [ 1 ∖ 1 ∖ 2 ] 2 } {\displaystyle f_{\zeta _{0}}(n)=\{n,n[1{\backslash }1{\backslash }2]2\}} f ϵ ζ 0 + 1 ( n ) = { n , n [ 1 ∖ 2 ∖ 2 ] 2 } {\displaystyle f_{\epsilon _{\zeta _{0}+1}}(n)=\{n,n[1{\backslash }2{\backslash }2]2\}} f ϵ ζ 0 + ω ( n ) = { n , n [ 1 ∖ 1 , 2 ∖ 2 ] 2 } {\displaystyle f_{\epsilon _{\zeta _{0}+\omega }}(n)=\{n,n[1{\backslash }1,2{\backslash }2]2\}} f ϵ ζ 0 + ϵ 0 ( n ) = { n , n [ 1 ∖ 1 [ 1 ∖ 2 ] 2 ∖ 2 ] 2 } {\displaystyle f_{\epsilon _{\zeta _{0}+\epsilon _{0}}}(n)=\{n,n[1{\backslash }1{[1{\backslash }2]}2{\backslash }2]2\}} f ϵ ζ 0 2 ( n ) = { n , n [ 1 ∖ 1 [ 1 ∖ 1 ∖ 2 ] 2 ∖ 2 ] 2 } {\displaystyle f_{\epsilon _{\zeta _{0}2}}(n)=\{n,n[1{\backslash }1{[1{\backslash }1{\backslash }2]}2{\backslash }2]2\}} f ϵ ϵ ζ 0 + 1 ( n ) = { n , n [ 1 ∖ 1 [ 1 ∖ 2 ∖ 2 ] 2 ∖ 2 ] 2 } {\displaystyle f_{\epsilon _{\epsilon _{\zeta _{0}+1}}}(n)=\{n,n[1{\backslash }1{[1{\backslash }2{\backslash }2]}2{\backslash }2]2\}} f ζ 1 ( n ) = { n , n [ 1 ∖ 1 ∖ 3 ] 2 } {\displaystyle f_{\zeta _{1}}(n)=\{n,n[1{\backslash }1{\backslash }3]2\}} f ζ ω ( n ) = { n , n [ 1 ∖ 1 ∖ 1 , 2 ] 2 } {\displaystyle f_{\zeta _{\omega }}(n)=\{n,n[1{\backslash }1{\backslash }1,2]2\}} f ζ ϵ 0 ( n ) = { n , n [ 1 ∖ 1 ∖ 1 [ 1 ∖ 2 ] 2 ] 2 } {\displaystyle f_{\zeta _{\epsilon _{0}}}(n)=\{n,n[1{\backslash }1{\backslash }1[1{\backslash }2]2]2\}} f ζ ζ 0 ( n ) = { n , n [ 1 ∖ 1 ∖ 1 [ 1 ∖ 1 ∖ 2 ] 2 ] 2 } {\displaystyle f_{\zeta _{\zeta _{0}}}(n)=\{n,n[1{\backslash }1{\backslash }1[1{\backslash }1{\backslash }2]2]2\}} f η 0 ( n ) = { n , n [ 1 ∖ 1 ∖ 1 ∖ 2 ] 2 } {\displaystyle f_{\eta _{0}}(n)=\{n,n[1{\backslash }1{\backslash }1{\backslash }2]2\}} f φ ( 4 , 0 ) ( n ) = { n , n [ 1 ∖ 1 ∖ 1 ∖ 1 ∖ 2 ] 2 } {\displaystyle f_{\varphi (4,0)}(n)=\{n,n[1{\backslash }1{\backslash }1{\backslash }1{\backslash }2]2\}} f φ ( m , 0 ) ( n ) = { n , n [ 1 ∖ 1 ∖ 1 ⋯ 1 ∖ 2 ] 2 } {\displaystyle f_{\varphi (m,0)}(n)=\{n,n[1{\backslash }1{\backslash }1{\cdots }1{\backslash }2]2\}} (m обратных слэшей) f φ ( ω , 0 ) ( n ) = { n , n [ 1 [ 2 ¬ 2 ] 2 ] 2 } {\displaystyle f_{\varphi (\omega ,0)}(n)=\{n,n[1[2{\neg }2]2]2\}} f ϵ φ ( ω , 0 ) + 1 ( n ) = { n , n [ 1 ∖ 2 [ 2 ¬ 2 ] 2 ] 2 } {\displaystyle f_{\epsilon _{\varphi (\omega ,0)+1}}(n)=\{n,n[1{\backslash }2[2{\neg }2]2]2\}} f ζ φ ( ω , 0 ) + 1 ( n ) = { n , n [ 1 ∖ 1 ∖ 2 [ 2 ¬ 2 ] 2 ] 2 } {\displaystyle f_{\zeta _{\varphi (\omega ,0)+1}}(n)=\{n,n[1{\backslash }1{\backslash }2[2{\neg }2]2]2\}} f η φ ( ω , 0 ) + 1 ( n ) = { n , n [ 1 ∖ 1 ∖ 1 ∖ 2 [ 2 ¬ 2 ] 2 ] 2 } {\displaystyle f_{\eta _{\varphi (\omega ,0)+1}}(n)=\{n,n[1{\backslash }1{\backslash }1{\backslash }2[2{\neg }2]2]2\}} f φ ( ω , 1 ) ( n ) = { n , n [ 1 [ 2 ¬ 2 ] 3 ] 2 } {\displaystyle f_{\varphi (\omega ,1)}(n)=\{n,n[1[2{\neg }2]3]2\}} f φ ( ω , 2 ) ( n ) = { n , n [ 1 [ 2 ¬ 2 ] 4 ] 2 } {\displaystyle f_{\varphi (\omega ,2)}(n)=\{n,n[1[2{\neg }2]4]2\}} f φ ( ω , ω ) ( n ) = { n , n [ 1 [ 2 ¬ 2 ] 1 , 2 ] 2 } {\displaystyle f_{\varphi (\omega ,\omega )}(n)=\{n,n[1[2{\neg }2]1,2]2\}} f φ ( ω , ϵ 0 ) ( n ) = { n , n [ 1 [ 2 ¬ 2 ] 1 [ 1 ∖ 2 ] 2 ] 2 } {\displaystyle f_{\varphi (\omega ,\epsilon _{0})}(n)=\{n,n[1[2{\neg }2]1[1{\backslash }2]2]2\}} f φ ( ω , ζ 0 ) ( n ) = { n , n [ 1 [ 2 ¬ 2 ] 1 [ 1 ∖ 1 ∖ 2 ] 2 ] 2 } {\displaystyle f_{\varphi (\omega ,\zeta _{0})}(n)=\{n,n[1[2{\neg }2]1[1{\backslash }1{\backslash }2]2]2\}} f φ ( ω , φ ( ω , 0 ) ) ( n ) = { n , n [ 1 [ 2 ¬ 2 ] 1 [ 1 [ 2 ¬ 2 ] 2 ] 2 ] 2 } {\displaystyle f_{\varphi (\omega ,\varphi (\omega ,0))}(n)=\{n,n[1[2{\neg }2]1[1[2{\neg }2]2]2]2\}} f φ ( ω , φ ( ω , φ ( ω , 0 ) ) ) ( n ) = { n , n [ 1 [ 2 ¬ 2 ] 1 [ 1 [ 2 ¬ 2 ] 1 [ 1 [ 2 ¬ 2 ] 2 ] 2 ] 2 ] 2 } {\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\}} f φ ( ω + 1 , 0 ) ( n ) = { n , n [ 1 [ 2 ¬ 2 ] 1 ∖ 2 ] 2 } {\displaystyle f_{\varphi (\omega +1,0)}(n)=\{n,n[1[2{\neg }2]1{\backslash }2]2\}} f φ ( ω + 2 , 0 ) ( n ) = { n , n [ 1 [ 2 ¬ 2 ] 1 ∖ 1 ∖ 2 ] 2 } {\displaystyle f_{\varphi (\omega +2,0)}(n)=\{n,n[1[2{\neg }2]1{\backslash }1{\backslash }2]2\}} f φ ( ω 2 , 0 ) ( n ) = { n , n [ 1 [ 2 ¬ 2 ] 1 [ 2 ¬ 2 ] 2 ] 2 } {\displaystyle f_{\varphi (\omega 2,0)}(n)=\{n,n[1[2{\neg }2]1[2{\neg }2]2]2\}} f φ ( ω 2 , 0 ) ( n ) = { n , n [ 1 [ 3 ¬ 2 ] 2 ] 2 } {\displaystyle f_{\varphi (\omega ^{2},0)}(n)=\{n,n[1[3{\neg }2]2]2\}} f φ ( ω 3 , 0 ) ( n ) = { n , n [ 1 [ 4 ¬ 2 ] 2 ] 2 } {\displaystyle f_{\varphi (\omega ^{3},0)}(n)=\{n,n[1[4{\neg }2]2]2\}} f φ ( ω ω , 0 ) ( n ) = { n , n [ 1 [ 1 , 2 ¬ 2 ] 2 ] 2 } {\displaystyle f_{\varphi (\omega ^{\omega },0)}(n)=\{n,n[1[1,2{\neg }2]2]2\}} f φ ( ω ω ω , 0 ) ( n ) = { n , n [ 1 [ 1 [ 2 ] 2 ¬ 2 ] 2 ] 2 } {\displaystyle f_{\varphi (\omega ^{\omega ^{\omega }},0)}(n)=\{n,n[1[1[2]2{\neg }2]2]2\}} f φ ( ϵ 0 , 0 ) ( n ) = { n , n [ 1 [ 1 [ 1 ∖ 2 ] 2 ¬ 2 ] 2 ] 2 } {\displaystyle f_{\varphi ({\epsilon _{0}},0)}(n)=\{n,n[1[1[1{\backslash }2]2{\neg }2]2]2\}} f Γ 0 ( n ) = { n , n [ 1 [ 1 ∖ 2 ¬ 2 ] 2 ] 2 } {\displaystyle f_{\Gamma _{0}}(n)=\{n,n[1[1{\backslash }2{\neg }2]2]2\}} f Γ 1 ( n ) = { n , n [ 1 [ 1 ∖ 2 ¬ 2 ] 3 ] 2 } {\displaystyle f_{\Gamma _{1}}(n)=\{n,n[1[1{\backslash }2{\neg }2]3]2\}} f Γ Γ 0 ( n ) = { n , n [ 1 [ 1 ∖ 2 ¬ 2 ] 1 [ 1 [ 1 ∖ 2 ¬ 2 ] 2 ] 2 ] 2 } {\displaystyle f_{\Gamma _{\Gamma _{0}}}(n)=\{n,n[1[1{\backslash }2{\neg }2]1[1[1{\backslash }2{\neg }2]2]2]2\}} f φ ( 1 , 1 , 0 ) ( n ) = { n , n [ 1 [ 1 ∖ 2 ¬ 2 ] 1 ∖ 2 ] 2 } {\displaystyle f_{\varphi (1,1,0)}(n)=\{n,n[1[1{\backslash }2{\neg }2]1{\backslash }2]2\}} f φ ( 1 , 2 , 0 ) ( n ) = { n , n [ 1 [ 1 ∖ 2 ¬ 2 ] 1 ∖ 1 ∖ 2 ] 2 } {\displaystyle f_{\varphi (1,2,0)}(n)=\{n,n[1[1{\backslash }2{\neg }2]1{\backslash }1{\backslash }2]2\}} f φ ( 2 , 0 , 0 ) ( n ) = { n , n [ 1 [ 1 ∖ 2 ¬ 2 ] 1 [ 1 ∖ 2 ¬ 2 ] 2 ] 2 } {\displaystyle f_{\varphi (2,0,0)}(n)=\{n,n[1[1{\backslash }2{\neg }2]1[1{\backslash }2{\neg }2]2]2\}} f φ ( ω , 0 , 0 ) ( n ) = { n , n [ 1 [ 2 ∖ 2 ¬ 2 ] 2 ] 2 } {\displaystyle f_{\varphi (\omega ,0,0)}(n)=\{n,n[1[2{\backslash }2{\neg }2]2]2\}} f φ ( Γ 0 , 0 , 0 ) ( n ) = { n , n [ 1 [ 1 [ 1 [ 1 ∖ 2 ¬ 2 ] 2 ] 2 ∖ 2 ¬ 2 ] 2 ] 2 } {\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\}} f φ ( 1 , 0 , 0 , 0 ) ( n ) = { n , n [ 1 [ 1 ∖ 3 ¬ 2 ] 2 ] 2 } {\displaystyle f_{\varphi (1,0,0,0)}(n)=\{n,n[1[1{\backslash }3{\neg }2]2]2\}} f φ ( 1 , 0 , 0 , 0 , 0 ) ( n ) = { n , n [ 1 [ 1 ∖ 4 ¬ 2 ] 2 ] 2 } {\displaystyle f_{\varphi (1,0,0,0,0)}(n)=\{n,n[1[1{\backslash }4{\neg }2]2]2\}} f ψ ( Ω Ω ω ) ( n ) = { n , n [ 1 [ 1 ∖ 1 , 2 ¬ 2 ] 2 ] 2 } ≈ T R E E ( n ) {\displaystyle f_{\psi (\Omega ^{\Omega ^{\omega }})}(n)=\{n,n[1[1{\backslash }1,2{\neg }2]2]2\}\approx TREE(n)} (см. TREE(3) ) f ψ ( Ω Ω ψ ( Ω Ω ) ) ( n ) = { n , n [ 1 [ 1 ∖ 1 [ 1 [ 1 ∖ 2 ¬ 2 ] 2 ] 2 ¬ 2 ] 2 ] 2 } {\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\}} f ψ ( Ω Ω Ω ) ( n ) = { n , n [ 1 [ 1 ∖ 1 ∖ 2 ¬ 2 ] 2 ] 2 } {\displaystyle f_{\psi (\Omega ^{\Omega ^{\Omega }})}(n)=\{n,n[1[1{\backslash }1{\backslash }2{\neg }2]2]2\}} f ψ ( Ω Ω Ω 2 ) ( n ) = { n , n [ 1 [ 1 ∖ 1 ∖ 1 ∖ 2 ¬ 2 ] 2 ] 2 } {\displaystyle f_{\psi (\Omega ^{\Omega ^{\Omega ^{2}}})}(n)=\{n,n[1[1{\backslash }1{\backslash }1{\backslash }2{\neg }2]2]2\}} f ψ ( Ω Ω Ω ω ) ( n ) = { n , n [ 1 [ 1 [ 2 ¬ 2 ] 2 ¬ 2 ] 2 ] 2 } {\displaystyle f_{\psi (\Omega ^{\Omega ^{\Omega ^{\omega }}})}(n)=\{n,n[1[1[2{\neg }2]2{\neg }2]2]2\}} f ψ ( Ω Ω Ω ψ ( Ω Ω Ω ) ) ( n ) = { n , n [ 1 [ 1 [ 1 [ 1 [ 1 ∖ 1 ∖ 2 ¬ 2 ] 2 ] 2 ¬ 2 ] 2 ¬ 2 ] 2 ] 2 } {\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\}} f ψ ( Ω Ω Ω Ω ) ( n ) = { n , n [ 1 [ 1 [ 1 ∖ 2 ¬ 2 ] 2 ¬ 2 ] 2 ] 2 } {\displaystyle f_{\psi (\Omega ^{\Omega ^{\Omega ^{\Omega }}})}(n)=\{n,n[1[1[1{\backslash }2{\neg }2]2{\neg }2]2]2\}} f ψ ( Ω 2 ) ( n ) = { n , n [ 1 [ 1 ¬ 3 ] 2 ] 2 } {\displaystyle f_{\psi (\Omega _{2})}(n)=\{n,n[1[1{\neg }3]2]2\}} f ψ ( Ω 2 + 1 ) ( n ) = { n , n [ 1 ∖ 2 [ 1 ¬ 3 ] 2 ] 2 } {\displaystyle f_{\psi (\Omega _{2}+1)}(n)=\{n,n[1{\backslash }2[1{\neg }3]2]2\}} f ψ ( Ω 2 + ω ) ( n ) = { n , n [ 1 ∖ 1 , 2 [ 1 ¬ 3 ] 2 ] 2 } {\displaystyle f_{\psi (\Omega _{2}+\omega )}(n)=\{n,n[1{\backslash }1,2[1{\neg }3]2]2\}} f ψ ( Ω 2 + ψ ( Ω Ω ) ) ( n ) = { n , n [ 1 ∖ 1 [ 1 [ 1 ∖ 2 ¬ 2 ] 2 ] 2 [ 1 ¬ 3 ] 2 ] 2 } {\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\}} f ψ ( Ω 2 + ψ ( Ω Ω ω ) ) ( n ) = { n , n [ 1 ∖ 1 [ 1 [ 1 ∖ 1 , 2 ¬ 2 ] 2 ] 2 [ 1 ¬ 3 ] 2 ] 2 } {\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\}} f ψ ( Ω 2 + ψ ( Ω Ω Ω ) ) ( n ) = { n , n [ 1 ∖ 1 [ 1 [ 1 ∖ 1 ∖ 2 ¬ 2 ] 2 ] 2 [ 1 ¬ 3 ] 2 ] 2 } {\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\}} f ψ ( Ω 2 + ψ ( Ω Ω Ω Ω ) ) ( n ) = { n , n [ 1 ∖ 1 [ 1 [ 1 [ 1 ∖ 2 ¬ 2 ] 2 ¬ 2 ] 2 ] 2 [ 1 ¬ 3 ] 2 ] 2 } {\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\}} f ψ ( Ω 2 + ψ ( Ω 2 ) ) ( n ) = { n , n [ 1 ∖ 1 [ 1 [ 1 ¬ 3 ] 2 ] 2 [ 1 ¬ 3 ] 2 ] 2 } {\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\}} f ψ ( Ω 2 + Ω ) ( n ) = { n , n [ 1 ∖ 1 ∖ 2 [ 1 ¬ 3 ] 2 ] 2 } {\displaystyle f_{\psi (\Omega _{2}+\Omega )}(n)=\{n,n[1{\backslash }1{\backslash }2[1{\neg }3]2]2\}} f ψ ( Ω 2 + Ω 2 ) ( n ) = { n , n [ 1 ∖ 1 ∖ 1 ∖ 2 [ 1 ¬ 3 ] 2 ] 2 } {\displaystyle f_{\psi (\Omega _{2}+\Omega ^{2})}(n)=\{n,n[1{\backslash }1{\backslash }1{\backslash }2[1{\neg }3]2]2\}} f ψ ( Ω 2 + Ω ω ) ( n ) = { n , n [ 1 [ 2 ¬ 2 ] 2 [ 1 ¬ 3 ] 2 ] 2 } {\displaystyle f_{\psi (\Omega _{2}+\Omega ^{\omega })}(n)=\{n,n[1[2{\neg }2]2[1{\neg }3]2]2\}} f ψ ( Ω 2 + Ω Ω ) ( n ) = { n , n [ 1 [ 1 ∖ 2 ¬ 2 ] 2 [ 1 ¬ 3 ] 2 ] 2 } {\displaystyle f_{\psi (\Omega _{2}+\Omega ^{\Omega })}(n)=\{n,n[1[1{\backslash }2{\neg }2]2[1{\neg }3]2]2\}} f ψ ( Ω 2 + ψ 1 ( Ω 2 ) ) ( n ) = { n , n [ 1 [ 1 ¬ 3 ] 3 ] 2 } {\displaystyle f_{\psi (\Omega _{2}+\psi _{1}(\Omega _{2}))}(n)=\{n,n[1[1{\neg }3]3]2\}} f ψ ( Ω 2 + ψ 1 ( Ω 2 + ψ 1 ( Ω 2 ) ) ) ( n ) = { n , n [ 1 [ 1 ¬ 3 ] 1 [ 1 ¬ 3 ] 2 ] 2 } {\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\}} f ψ ( Ω 2 + ψ 1 ( Ω 2 + ψ 1 ( Ω 2 + 1 ) ) ) ( n ) = { n , n [ 1 [ 2 ¬ 3 ] 2 ] 2 } {\displaystyle f_{\psi (\Omega _{2}+\psi _{1}(\Omega _{2}+\psi _{1}(\Omega _{2}+1)))}(n)=\{n,n[1[2{\neg }3]2]2\}} f ψ ( Ω 2 + ψ 1 ( Ω 2 + ψ 1 ( Ω 2 + ψ 1 ( Ω 2 ) ) ) ) ( n ) = { n , n [ 1 [ 1 [ 1 ¬ 3 ] 2 ¬ 3 ] 2 ] 2 } {\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\}} f ψ ( Ω 2 2 ) ( n ) = { n , n [ 1 [ 1 ¬ 4 ] 2 ] 2 } {\displaystyle f_{\psi (\Omega _{2}2)}(n)=\{n,n[1[1{\neg }4]2]2\}} f ψ ( Ω 2 3 ) ( n ) = { n , n [ 1 [ 1 ¬ 5 ] 2 ] 2 } {\displaystyle f_{\psi (\Omega _{2}3)}(n)=\{n,n[1[1{\neg }5]2]2\}} f ψ ( Ω 2 ω ) ( n ) = { n , n [ 1 [ 1 ¬ 1 , 2 ] 2 ] 2 } {\displaystyle f_{\psi (\Omega _{2}\omega )}(n)=\{n,n[1[1{\neg }1,2]2]2\}} f ψ ( Ω 2 ψ ( 0 ) ) ( n ) = { n , n [ 1 [ 1 ¬ 1 [ 1 ∖ 2 ] 2 ] 2 ] 2 } {\displaystyle f_{\psi (\Omega _{2}\psi (0))}(n)=\{n,n[1[1{\neg }1[1{\backslash }2]2]2]2\}} f ψ ( Ω 2 ψ ( Ω Ω ) ) ( n ) = { n , n [ 1 [ 1 ¬ 1 [ 1 [ 1 ∖ 2 ¬ 2 ] 2 ] 2 ] 2 ] 2 } {\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\}} f ψ ( Ω 2 ψ ( Ω 2 ) ) ( n ) = { n , n [ 1 [ 1 ¬ 1 [ 1 [ 1 ¬ 3 ] 2 ] 2 ] 2 ] 2 } {\displaystyle f_{\psi (\Omega _{2}\psi (\Omega _{2}))}(n)=\{n,n[1[1{\neg }1[1[1{\neg }3]2]2]2]2\}} f ψ ( Ω 2 Ω ) ( n ) = { n , n [ 1 [ 1 ¬ 1 ∖ 2 ] 2 ] 2 } {\displaystyle f_{\psi (\Omega _{2}\Omega )}(n)=\{n,n[1[1{\neg }1{\backslash }2]2]2\}} f ψ ( Ω 2 Ω Ω ) ( n ) = { n , n [ 1 [ 1 ¬ 1 [ 1 ∖ 2 ¬ 2 ] 2 ] 2 ] 2 } {\displaystyle f_{\psi (\Omega _{2}\Omega ^{\Omega })}(n)=\{n,n[1[1{\neg }1[1{\backslash }2{\neg }2]2]2]2\}} f ψ ( Ω 2 ψ 1 ( Ω 2 ) ) ( n ) = { n , n [ 1 [ 1 ¬ 1 [ 1 ¬ 3 ] 2 ] 2 ] 2 } {\displaystyle f_{\psi (\Omega _{2}\psi _{1}(\Omega _{2}))}(n)=\{n,n[1[1{\neg }1[1{\neg }3]2]2]2\}} f ψ ( Ω 2 2 ) ( n ) = { n , n [ 1 [ 1 ¬ 1 ¬ 2 ] 2 ] 2 } {\displaystyle f_{\psi (\Omega _{2}^{2})}(n)=\{n,n[1[1{\neg }1{\neg }2]2]2\}} f ψ ( Ω 2 ω ) ( n ) = { n , n [ 1 [ 1 [ 2 ∖ 3 2 ] 2 ] 2 ] 2 } {\displaystyle f_{\psi (\Omega _{2}^{\omega })}(n)=\{n,n[1[1[2{\backslash }_{3}2]2]2]2\}} f ψ ( Ω 2 Ω 2 ) ( n ) = { n , n [ 1 [ 1 [ 1 ∖ 2 2 ∖ 3 2 ] 2 ] 2 ] 2 } {\displaystyle f_{\psi (\Omega _{2}^{\Omega _{2}})}(n)=\{n,n[1[1[1{\backslash }_{2}2{\backslash }_{3}2]2]2]2\}} f ψ ( Ω 3 ) ( n ) = { n , n [ 1 [ 1 [ 1 ∖ 3 3 ] 2 ] 2 ] 2 } {\displaystyle f_{\psi (\Omega _{3})}(n)=\{n,n[1[1[1{\backslash }_{3}3]2]2]2\}} f ψ ( Ω 3 Ω 3 ) ( n ) = { n , n [ 1 [ 1 [ 1 [ 1 ∖ 3 2 ∖ 4 2 ] 2 ] 2 ] 2 ] 2 } {\displaystyle f_{\psi (\Omega _{3}^{\Omega _{3}})}(n)=\{n,n[1[1[1[1{\backslash }_{3}2{\backslash }_{4}2]2]2]2]2\}} f ψ ( Ω 4 ) ( n ) = { n , n [ 1 [ 1 [ 1 [ 1 ∖ 4 3 ] 2 ] 2 ] 2 ] 2 } {\displaystyle f_{\psi (\Omega _{4})}(n)=\{n,n[1[1[1[1{\backslash }_{4}3]2]2]2]2\}} f ψ ( Ω ω ) ( n ) = { n , n [ 1 [ 2 ∖ 1 , 2 2 ] 2 ] 2 } {\displaystyle f_{\psi (\Omega _{\omega })}(n)=\{n,n[1[2{\backslash }_{1,2}2]2]2\}} f ψ ( Ω ψ ( Ω ) ) ( n ) = { n , n [ 1 [ 2 ∖ 1 [ 1 ∖ 2 ] 2 2 ] 2 ] 2 } {\displaystyle f_{\psi (\Omega _{\psi (\Omega )})}(n)=\{n,n[1[2{\backslash }_{1[1{\backslash }2]2}2]2]2\}} f ψ ( Ω ψ ( Ω ψ ( Ω ) ) ) ( n ) = { n , n [ 1 [ 2 ∖ 1 [ 2 ∖ 1 [ 1 ∖ 2 ] 2 2 ] 2 2 ] 2 ] 2 } {\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\}} f ψ ( Ω Ω ) ( n ) = { n , n [ 1 [ 2 ∖ 1 ∖ 2 2 ] 2 ] 2 } = ( 0 , 0 , 0 ) ( 1 , 1 , 1 ) ( 2 , 1 , 1 ) ( 3 , 1 , 0 ) [ n ] {\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]} (см. Bashicu Matrix System ) f ψ ( Ω Ω 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 ] {\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]} f ψ ( Ω Ω ω ) ( n ) = ( 0 , 0 , 0 ) ( 1 , 1 , 1 ) ( 2 , 1 , 1 ) ( 3 , 1 , 0 ) ( 1 , 1 , 1 ) [ n ] {\displaystyle f_{\psi ({\Omega _{\Omega _{\omega }}})}(n)=(0,0,0)(1,1,1)(2,1,1)(3,1,0)(1,1,1)[n]} f ψ ( Ω Ω Ω ) ( n ) = ( 0 , 0 , 0 ) ( 1 , 1 , 1 ) ( 2 , 1 , 1 ) ( 3 , 1 , 0 ) ( 1 , 1 , 1 ) ( 2 , 1 , 1 ) ( 3 , 1 , 0 ) [ n ] {\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]} f ψ ( ψ I ( 0 ) ) ( n ) = ( 0 , 0 , 0 ) ( 1 , 1 , 1 ) ( 2 , 1 , 1 ) ( 3 , 1 , 0 ) ( 2 , 0 , 0 ) [ n ] {\displaystyle 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. Cichon, E. A.; Wainer, S. S. (1983), "The slow-growing and the Grzegorczyk hierarchies", The Journal of Symbolic Logic , 48 (2): 399—408, doi :10.2307/2273557 , ISSN 0022-4812 , MR 0704094 Gallier, Jean H. (1991), "What's so special about Kruskal's theorem and the ordinal Γ0 ? A survey of some results in proof theory" , Ann. Pure Appl. Logic , 53 (3): 199—260, doi :10.1016/0168-0072(91)90022-E , MR 1129778 (недоступная ссылка) 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), "Π1 2 -logic. I. Dilators", Annals of Mathematical Logic , 21 (2): 75—219, doi :10.1016/0003-4843(81)90016-4 , ISSN 0003-4843 , MR 0656793 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. Числа Функции Нотации