急成長階層

急成長階層（きゅうせいちょうかいそう、テンプレート:Lang-en-short）および拡張グジェゴルチク階層（かくちょうグジェゴルチクかいそう、テンプレート:Lang-en-short）とは、1970年にマーティン・レーペ（Martin Löb）とスタンリー・S・ウェイナーによって定義された、最大 ${\mathrm{\aleph }}_1$ 層からなる計算可能関数の階層である。急成長階層の定義にはいくつかのバージョンがあるが、特にウェイナーが テンプレート:Math の範囲について1972年の論文で定義し、ケトネンとソロヴェイが簡略化したバージョンをウェイナー階層（テンプレート:Lang-en-short）と呼ぶ。

急成長階層の定義に登場する、可算な順序数で添字づけられた計算可能関数の族 $\{f_{\alpha }{\}}_{\alpha <\tau }$（テンプレート:Math は適当な極限順序数）を急増加関数と呼ぶ。

定義

以下の関数 テンプレート:Math の定義はケトネンとソロヴェイの論文による。極限順序数 テンプレート:Math の基本列とは、自然数で添え字づけられた順序数の単調増加列 テンプレート:Math であって テンプレート:Math に収束するものである。

極限順序数 テンプレート:Math と自然数 テンプレート:Mvar に対して テンプレート:Math を以下で定義する：

• テンプレート:Math が $\alpha ={\omega }^{\beta +1}\cdot (\gamma +1)$ と書ける場合、$\alpha [n]={\omega }^{\beta +1}\cdot \gamma +{\omega }^{\beta }\cdot n$。
• テンプレート:Math が $\alpha ={\omega }^{\beta }\cdot (\gamma +1)$ （テンプレート:Math は極限順序数）と書ける場合、$\alpha [n]={\omega }^{\beta }\cdot \gamma +{\omega }^{\beta [n]}$。
• テンプレート:Math の場合、$\alpha [0]=1,\alpha [n+1]={\omega }^{\alpha [n]}$。

順序数 テンプレート:Math に対して、自然数上の関数 $f_{\alpha }:\mathbb{N}\to \mathbb{N}$ を次のように定義する：

• $f_0(n)=n+1$
• $f_{\alpha +1}(n)=f_{\alpha }^{1+n}(n)$
• $f_{\alpha }(n)=f_{\alpha [n]}(n)$　（テンプレート:Math が極限順序数の場合）

ただし テンプレート:Math に対して$f_{\alpha }^n(n)=\underset{n}{\underbrace{f_{\alpha }(f_{\alpha }(\dots (f_{\alpha }(n))\dots ))}}$とする。

計算可能関数の集合 ${ℱ}_{\alpha }$は、テンプレート:Math を含み、ゼロ関数・後者関数・射影関数・関数の合成・限定再帰で閉じた最小の集合として定義される（グジェゴルチク階層も参照）。

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

• 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 を参照)

関連項目

• 巨大数
• 順序数
• ハーディ階層
• 緩成長階層