WikiSort.ru - Не сортированное

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

Определение

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

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

${\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}$ .

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

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

В частности при n=10^[1]

${\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}$ ,

${\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}$ ,

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

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

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

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

	нотация Кнута	нотация Конвея	нотация Бауэрса
предел нотации	${\displaystyle \omega }$	${\displaystyle \omega ^{2}}$	${\displaystyle \omega ^{\omega }}$
примеры	${\displaystyle f_{\omega }(10)\approx 10\uparrow ^{9}11=10\uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \uparrow 11}$	${\displaystyle f_{\omega ^{2}}(n)\approx \underbrace {n\rightarrow n\rightarrow n\cdots \rightarrow n} _{n+1\quad \rightarrow }}$	${\displaystyle f_{\omega ^{\omega }}(n)\approx \underbrace {\{n,n,n,\cdots ,n,n\}} _{n+2\quad n's}}$
	${\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}}}$	${\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}}}$	${\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}}}$

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

Примечания

Ссылки

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