急成長階層（きゅうせいちょうかいそう、英: fast-growing hierarchy）および拡張グジェゴルチク階層（かくちょうグジェゴルチクかいそう、英: extended Grzegorczyk hierarchy）とは、1970年にマーティン・レーペ（Martin Lob）とスタンリー・S・ウェイナーによって定義された[1]、最大 ℵ 1 {\displaystyle \aleph _{1}} 層からなる計算可能関数の階層である。急成長階層の定義にはいくつかのバージョンがあるが、特にウェイナーが α ≦ ε0 の範囲について1972年の論文[2]で定義し、ケトネンとソロヴェイが簡略化した[3]バージョンをウェイナー階層（英: Wainer hierarchy）と呼ぶ[4]。

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

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

極限順序数 α (≦ ε0) と自然数 n に対して α[n] を以下で定義する：

α が α = ω β + 1 ⋅ ( γ + 1 ) {\displaystyle \alpha =\omega ^{\beta +1}\cdot (\gamma +1)} と書ける場合、 α [ n ] = ω β + 1 ⋅ γ + ω β ⋅ n {\displaystyle \alpha [n]=\omega ^{\beta +1}\cdot \gamma +\omega ^{\beta }\cdot n} 。

α が α = ω β ⋅ ( γ + 1 ) {\displaystyle \alpha =\omega ^{\beta }\cdot (\gamma +1)} （β は極限順序数）と書ける場合、 α [ n ] = ω β ⋅ γ + ω β [ n ] {\displaystyle \alpha [n]=\omega ^{\beta }\cdot \gamma +\omega ^{\beta [n]}} 。

α = ε0 の場合、 α [ 0 ] = 1 ,   α [ n + 1 ] = ω α [ n ] {\displaystyle \alpha [0]=1,\ \alpha [n+1]=\omega ^{\alpha [n]}} 。

順序数 α (≦ ε0) に対して、自然数上の関数 f α : N → N {\displaystyle f_{\alpha }:\mathbb {N} \to \mathbb {N} } を次のように定義する：

f 0 ( n ) = n + 1 {\displaystyle f_{0}(n)=n+1}

f α + 1 ( n ) = f α 1 + n ( n ) {\displaystyle f_{\alpha +1}(n)=f_{\alpha }^{1+n}(n)}

f α ( n ) = f α [ n ] ( n ) {\displaystyle f_{\alpha }(n)=f_{\alpha [n]}(n)} 　（α が極限順序数の場合）

ただし n > 0 に対して f α n ( n ) = f α ( f α ( … ( f α ( n ) ) … ) ) ⏟ n {\displaystyle f_{\alpha }^{n}(n)=\underbrace {f_{\alpha }(f_{\alpha }(\dots (f_{\alpha }(n))\dots ))} _{n}} とする。

計算可能関数の集合 F α {\displaystyle {\mathcal {F}}_{\alpha }} は、fα を含み、ゼロ関数・後者関数・射影関数・関数の合成・限定再帰で閉じた最小の集合として定義される（グジェゴルチク階層も参照）。
他の巨大数の表記法との比較

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

関連項目

巨大数

順序数

ハーディ階層

緩成長階層

参考文献^ Lob, M. H.; Wainer, S. S. (1970-03-01). “Hierarchies of number-theoretic functions. I” (英語). Archiv fur mathematische Logik und Grundlagenforschung 13 (1): 39?51. doi:10.1007/BF01967649. .mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation.cs-ja1 q,.mw-parser-output .citation.cs-ja2 q{quotes:"「""」""『""』"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free a,.mw-parser-output .citation .cs1-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/6/65/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited a,.mw-parser-output .id-lock-registration a,.mw-parser-output .citation .cs1-lock-limited a,.mw-parser-output .citation .cs1-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/d/d6/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription a,.mw-parser-output .citation .cs1-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/a/aa/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("//upload.wikimedia.org/wikipedia/commons/4/4c/Wikisource-logo.svg")right 0.1em center/12px no-repeat}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:#d33}.mw-parser-output .cs1-visible-error{color:#d33}.mw-parser-output .cs1-maint{display:none;color:#3a3;margin-left:0.3em}.mw-parser-output .cs1-format{font-size:95%}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}ISSN 1432-0665. https://doi.org/10.1007/BF01967649. 
^ Wainer, S. S. (1972). “Ordinal Recursion, and a Refinement of the Extended Grzegorczyk Hierarchy”. The Journal of Symbolic Logic 37 (2): 281?292. doi:10.2307/2272973. ISSN 0022-4812. https://www.jstor.org/stable/2272973. 
^ a b Ketonen, Jussi; Solovay, Robert (1981). “Rapidly Growing Ramsey Functions”. Annals of Mathematics 113 (2): 267?314. doi:10.2307/2006985. ISSN 0003-486X. https://www.jstor.org/stable/2006985. 
^ “Fast growing functions based on Ramsey theorems” (英語). Discrete Mathematics 95 (1-3): 341?358. (1991-12-03). doi:10.1016/0012-365X(91)90346-4. ISSN 0012-365X. https://www.sciencedirect.com/science/article/pii/0012365X91903464. 
.mw-parser-output .asbox{position:relative;overflow:hidden}.mw-parser-output .asbox table{background:transparent}.mw-parser-output .asbox p{margin:0}.mw-parser-output .asbox p+p{margin-top:0.25em}.mw-parser-output .asbox{font-size:90%}.mw-parser-output .asbox-note{font-size:90%}.mw-parser-output .asbox .navbar{position:absolute;top:-0.90em;right:1em;display:none}

この項目は、数学に関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（プロジェクト:数学／Portal:数学）。
.mw-parser-output .hlist ul,.mw-parser-output .hlist ol{padding-left:0}.mw-parser-output .hlist li,.mw-parser-output .hlist dd,.mw-parser-output .hlist dt{margin-right:0;display:inline-block;white-space:nowrap}.mw-parser-output .hlist dt:after,.mw-parser-output .hlist dd:after,.mw-parser-output .hlist li:after{white-space:normal}.mw-parser-output .hlist li:after,.mw-parser-output .hlist dd:after{content:" ・\a0 ";font-weight:bold}.mw-parser-output .hlist dt:after{content:": "}.mw-parser-output .hlist-pipe dd:after,.mw-parser-output .hlist-pipe li:after{content:" |\a0 ";font-weight:normal}.mw-parser-output .hlist-hyphen dd:after,.mw-parser-output .hlist-hyphen li:after{content:" -\a0 ";font-weight:normal}.mw-parser-output .hlist-comma dd:after,.mw-parser-output .hlist-comma li:after{content:"、";font-weight:normal}.mw-parser-output .hlist-slash dd:after,.mw-parser-output .hlist-slash li:after{content:" /\a0 ";font-weight:normal}.mw-parser-output .hlist dd:last-child:after,.mw-parser-output .hlist dt:last-child:after,.mw-parser-output .hlist li:last-child:after{content:none}.mw-parser-output .hlist dd dd:first-child:before,.mw-parser-output .hlist dd dt:first-child:before,.mw-parser-output .hlist dd li:first-child:before,.mw-parser-output .hlist dt dd:first-child:before,.mw-parser-output .hlist dt dt:first-child:before,.mw-parser-output .hlist dt li:first-child:before,.mw-parser-output .hlist li dd:first-child:before,.mw-parser-output .hlist li dt:first-child:before,.mw-parser-output .hlist li li:first-child:before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child:after,.mw-parser-output .hlist dd dt:last-child:after,.mw-parser-output .hlist dd li:last-child:after,.mw-parser-output .hlist dt dd:last-child:after,.mw-parser-output .hlist dt dt:last-child:after,.mw-parser-output .hlist dt li:last-child:after,.mw-parser-output .hlist li dd:last-child:after,.mw-parser-output .hlist li dt:last-child:after,.mw-parser-output .hlist li li:last-child:after{content:")\a0 ";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li:before{content:" "counter(listitem)" ";white-space:nowrap}.mw-parser-output .hlist dd ol>li:first-child:before,.mw-parser-output .hlist dt ol>li:first-child:before,.mw-parser-output .hlist li ol>li:first-child:before{content:" ("counter(listitem)" "}.mw-parser-output .navbar{display:inline;font-size:75%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}.mw-parser-output .infobox .navbar{font-size:88%}.mw-parser-output .navbox .navbar{display:block;font-size:88%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}