急成長階層
順序数 α (≦ ε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α を含み、ゼロ関数・後者関数・射影関数・関数の合成・限定再帰で閉じた最小の集合として定義される(グジェゴルチク階層も参照)。