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

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

Определение

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

  1. f0(n)=n+1 (в общем случае f0(n) может быть любой растущей функцией),
  2. fα+1(n)=fαn(n)=fα(fα((fα(fα(n разn)))),
  3. fα(n)=fα[n](n) если α предельный ординал,
    • где α[n] является n-ым элементом фундаментальной последовательности, установленной для некого предельного ординала α.
    • Существуют различные версии быстрорастущей иерархии, однако наиболее известной является иерархия Лёба-Вайнера, в которой фундаментальные последовательности для предельных ординалов, записанных в нормальной форме Кантора, определяются следующими правилами

  4. ω[n]=n,
  5. (ωα1+ωα2++ωαk1+ωαk)[n]=ωα1+ωα2++ωαk1+ωαk[n]
    • для α1α2αk,

  6. ωα+1[n]=ωαn,
  7. ωα[n]=ωα[n] если α предельный ординал,
  8. ε0[0]=0 и ε0[n+1]=ωε0[n]=ω↑↑n.

Примеры

f1(n)=f0n(n)=f0(f0((f0(f0(nf0n))))=2×n, f2(n)=f1n(n)=f1(f1((f1(f1(nf1n))))=2n×n. Для функций, индексированных конечными ординалами α>1 верно fm(n)>2m1n. В частности при n=10 f3(10)=f210(10)10101010103.48910десяток10↑↑11, f4(10)=f310(10)10101010103.48910101010103.48910101010103.48910десяток}10 нижних фигурных скобок10↑↑↑11, fm(10)10m111. Таким образом, уже первый трансфинитный ординал ω соответствует пределу стрелочной нотации Кнута. Знаменитое число Грэма меньше, чем fω+1(64). Благодаря простоте и ясности определения быстрорастущая иерархия применяется для анализа различных нотаций для записи больших чисел.
нотация Кнутанотация Конвеянотация Бауэрса\tabularnewline предел нотацииωω2ωω\tabularnewline примерыfω(10)10911=10↑↑↑↑↑↑↑↑↑11fω2(n)nnnnn+1fωω(n){n,n,n,,n,n}n+2ns\tabularnewline $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\}}
Данная выше дефиниция определяет быстрорастущую иерархию до ε0=ω↑↑n. Для дальнейшего роста можно использовать функцию Веблена и другие, еще более мощные нотации для ординалов.