急成長階層

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

急成長階層の定義に登場する、可算な順序数で添字づけられた計算可能関数の族 （ は適当な極限順序数）を急増加関数と呼ぶ。 

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

極限順序数  と自然数  に対して  を以下で定義する：

  が  と書ける場合、。
  が  （ は極限順序数）と書ける場合、。
  の場合、。

順序数  に対して、自然数上の関数  を次のように定義する：



 　（ が極限順序数の場合）

ただし  に対してとする。

計算可能関数の集合 は、 を含み、ゼロ関数・後者関数・射影関数・関数の合成・限定再帰で閉じた最小の集合として定義される（グジェゴルチク階層も参照）。

 他の巨大数の表記法との比較 
 f0(n)=n+1
f1(n)=f0n(n)=n+(1·n)=2n
f2(n)=f1n(n)=2(2(...2(n)...))=2nn>2↑n (クヌースの矢印表記 を参照)
f3(n)=f2n(n)>2↑↑n
fω(n)=fn-1n(n)>2 ↑n-1 n ≒ {n,n,n-1} (配列表記・BEAF を参照)

 関連項目 
 巨大数
 順序数
 ハーディ階層
 緩成長階層

 参考文献 

Category:巨大数
Category:計算可能性理論
Category:証明論
Category:数学に関する記事