急成長階層

急成長階層(きゅうせいちょうかいそう、英: fast-growing hierarchy、急増加関数(きゅうぞうかかんすう)とも訳される)および拡張グジェゴルチク階層(かくちょうぐじぇごるちくかいそう、英: extended Grzegorczyk hierarchy)とは、順序数 α に対して f_α: N → N （ N は 自然数 )を定める関数の階層である。最も標準的なものは、全てのα< ε₀に対しての拡張である Wainer階層である。

定義

急成長階層f_αは、次のように定義される。

${\begin{aligned}&f_{0}(n)=n+1\\&f_{\alpha +1}(n)=f_{\alpha }^{n}(n)\\&f_{\alpha }(n)=f_{\alpha [n]}(n)\end{aligned}}$

ここで、$f_{\alpha }^{n}(n)=\underbrace {f_{\alpha }(f_{\alpha }(\dots (f_{\alpha }(n))\dots ))} _{n}$とし、$\alpha [n]$は、極限順序数αの基本列のn番目とする。

Wainer階層

Wainer階層は、α ≤ ε₀となるαに対し、次のように基本列を定義する事によって得られる急成長階層である。

カントール標準形で書かれている極限順序数λ<ε₀ の基本列λ[n]は

1. λ=ω^α₁+...+ω^α_k-1+ω^α_k のとき、 λ[n]=ω^α₁+...+ω^α_k-1+ω^α_k[n] (但し、α₁≥...≥α_k-1≥α_k)
2. λ=ω^α+1のとき、λ[n]=ω^αn
3. λ=ω^α(αは極限順序数)のとき、λ[n]=ω^α[n]
4. λ=ε₀のとき、基本列λ[n]は、

• λ[0]=1
• λ[n+1]=ω^λ[n]

例

$(\omega ^{\omega }+{\omega ^{\omega ^{\omega ^{\omega +1}+{\omega }+2}}})[n]=\omega ^{\omega }+{\omega ^{\omega ^{\omega ^{\omega +1}+{\omega }+2}}}[n]$(1.を使用)

${\textstyle \omega ^{\omega }+{\omega ^{\omega ^{\omega ^{\omega +1}+{\omega }+2}}}[n]=\omega ^{\omega }+{\omega ^{(\omega ^{\omega ^{\omega +1}+{\omega }+2})[n]}}}$(3.を使用)

${\textstyle \qquad \qquad \qquad \qquad \,=\omega ^{\omega }+{\omega ^{(\omega ^{(\omega ^{\omega +1}+{\omega }+1)+1})[n]}}}$

${\textstyle \qquad \qquad \qquad \qquad \,=\omega ^{\omega }+{\omega ^{(\omega ^{(\omega ^{\omega +1}+{\omega }+1)})n}}}$(2.を使用)

他の巨大数の表記法との比較

• f₀(n)=n+1
• f₁(n)=f₀ⁿ(n)=n+(1·n)=2n
• f₂(n)=f₁ⁿ(n)=2(2(...2(n)...))=2ⁿn>2↑n (クヌースの矢印表記 を参照)
• f₃(n)=f₂ⁿ(n)>2↑↑n
• f_ω(n)=f_n-1ⁿ(n)>2 ↑^n-1 n ≒ {n,n,n-1} (配列表記・BEAF を参照)