急速に成長する階層

計算可能性理論、計算複雑性理論、証明理論において、急増加階層（拡張グジェゴルチク階層、シュヴィッテンベルク・ワイナー階層とも呼ばれる）^[1]は、急速に増加する関数f _α : N → N（ここでNは自然数集合{0, 1, ...}、αはある大きな可算順序数までの範囲）の順序数インデックス付きファミリである。主な例はワイナー階層、またはレーブ・ワイナー階層で、これはすべてのα < ε ₀への拡張である。このような階層は、成長率と計算複雑性に従って計算可能関数を分類する自然な方法を提供する。

μ を大きな可算順序数とし、あらゆる極限順序数α < μ に基本列(上限が α である順序数の厳密に増加する列)が割り当てられるとします。α < μ の場合、関数の急成長階層f _α : N → Nは次のように定義されます。

• ${\displaystyle f_{0}(n)=n+1,}$
• ${\displaystyle f_{\alpha +1}(n)=f_{\alpha }^{n}(n)}$
• ${\displaystyle f_{\alpha }(n)=f_{\alpha [n]}(n)}$α が極限順序数の場合。

ここで、f _α ⁿ ( n ) = f _α ( f _α (...( f _α ( n ))...)) は、nに適用されるf _αの n^回 目の反復を表し、 α[ n ] は、極限順序数 α に割り当てられた基本シーケンスのn^番目の要素を表します。 (別の定義では、上記の 2 行目の nではなく、反復回数をn +1 とします。)

この階層の最初の部分は、有限のインデックスを持つ関数f _α (つまり、 α < ω)で構成され、 Grzegorczyk 階層と密接な関係があるため、しばしばGrzegorczyk 階層と呼ばれます。ただし、前者はここではインデックス付きの関数f _nの族であるのに対し、後者はインデックス付きの関数の集合の族であることに注意してください。(以下の「興味のある点」を参照してください。) ${\displaystyle {\mathcal {E}}^{n}}$

上記の定義をさらに一般化すると、f _{0 を}任意の非減少関数 g: N → Nとすることで、高速反復階層が得られます。

ε ₀以下の極限順序数については、基本シーケンスの簡単な自然な定義があります (以下のワイナー階層を参照)。しかし、ε _{0 を}超えると定義ははるかに複雑になります。ただし、これは、フェファーマン-シュッテ順序数Γ _{0 を}はるかに超えて、少なくともバッハマン-ハワード順序数まで可能です。ブッフホルツの psi 関数を使用すると、この定義を超限反復 -内包の順序数に簡単に拡張できます(解析階層を参照)。 ${\displaystyle \Pi _{1}^{1}}$

再帰的順序数を超えて完全に指定された拡張はありそうにないと考えられています。たとえば、Prڧmel et al. [1991](p. 348) は、そのような試みでは「順序表記に問題が生じる可能性さえある」と述べています。

ワイナー階層は、関数f _α（α ≤ ε ₀ ）の特定の急成長階層であり、次のように基本列を定義することによって得られます[Gallier 1991][Prڧmel, et al., 1991]。

極限序数 λ < ε ₀の場合、カントール正規形で記述され、

• α ₁ ≥ ... ≥ α ^k ₋₁ ≥ α ^_kの場合、 λ = ω ^{α ₁} + ... + ω α k ^₋₁ + ω ^α _kの場合、 λ[ n ] = ω ^{α ₁} + ... + ω ^{α _k−1} + ω ^{α _k} [ n ]、
• λ = ω ^α+1の場合、 λ[ n ] = ω ^α n、
• 極限順序 α に対してλ = ω ^{αの場合、 λ[} n ] = ω ^{α[ n ]}、

そして

• λ = ε ₀の場合、 [Gallier 1991] のようにλ[0] = 0 および λ[ n + 1] = ω ^{λ[ n ]}とします。あるいは、[Prãmel, et al., 1991] のように λ[0] = 1 で始まることを除いて同じシーケンスを使用します。n
  > 0の場合、代替バージョンでは、結果として得られる指数関数タワーに 1 つの追加の ω が含まれます。つまり、n 個のオメガを含む λ[ n ] = ω ^{ω ⋰ ω}となります。

著者によっては若干異なる定義（例えば、 ωαnではなく^ωα+1 [ n ]= ^ωα ( ⁿ +1 )）を使用し、α<ε0の場合にのみこの階層を定義する_（したがってfε0を階層から除外する）_著者もいる。

ε _{0 を}超えて続けるには、ヴェブレン階層の基本シーケンスを参照してください。

急速に成長する階層に関する興味深いポイントをいくつか次に示します。

• すべてのf _{α は}全関数です。基本シーケンスが計算可能であれば（たとえば、ワイナー階層の場合のように）、すべてのf _αは全計算可能関数です。
• ワイナー階層では、 α < β の場合、 f _αはf _βによって支配されます。(任意の 2 つの関数f、g : N → Nに対して、十分に大きいnに対してf ( n ) > g ( n )である場合、f はg を支配する と言われています。) 同じ特性は、いわゆるバッハマン特性を満たす基本シーケンスを持つ任意の急成長階層で当てはまります。(この特性は、ほとんどの自然な順序付けで当てはまります。) ^{[説明が必要]}
• Grzegorczyk 階層では、すべての原始再帰関数は、α < ω であるf _αによって支配されます。したがって、 Wainer 階層では、すべての原始再帰関数は、 Ackermann 関数の変形であるf _ωによって支配されます。
• n ≥ 3の場合、 Grzegorczyk 階層内のセットは、十分に大きな引数に対して、最大引数で評価される固定反復f _{n -1} ^kによって制限された時間内に計算可能な、合計多引数関数のみで構成されます。${\displaystyle {\mathcal {E}}^{n}}$
• ワイナー階層では、α < ε ₀となるすべてのf _{α は}計算可能であり、ペアノ算術で全であることが証明できます。
• ペアノ算術で証明可能全体であるすべての計算可能関数は、ワイナー階層でα < ε ₀であるf _αによって支配されます。したがって、ワイナー階層のf _{ε 0 は}、ペアノ算術では証明可能全体ではありません。
• グッドスタイン関数は、ワイナー階層におけるf _{ε 0}とほぼ同じ成長率（すなわち、それぞれが他方の固定反復によって支配される）^[要出典]を持ち、 α < ε ₀であるすべてのf _{α を}支配するため、ペアノ算術では完全には証明できない。
• ワイナー階層では、α < β < ε ₀の場合、f _{β は}、ある固定反復f _α ^kによって制限される時間と空間内のすべての計算可能な関数を支配します。
• フリードマンのTREE関数は、ガリエ（1991）によって記述された急成長階層においてf _{Γ 0を支配します。}
• 関数f _αのワイナー階層と関数h _αのハーディ階層は、すべての α < ε ₀に対してf _α = h _{ω ^α}で関連しています。ハーディ階層は α = ε ₀でワイナー階層に「追いつき」、つまり、すべてのn ≥ 1 に対してf _{ε 0} ( n -1) ≤ h _{ε 0} ( n ) ≤ f _{ε 0} ( n +1)という意味で、f _{ε 0}とh _{ε 0}は同じ成長率を持ちます。 (Gallier 1991)
• Girard (1981) と Cichon & Wainer (1983) は、関数g _αの緩やかな増加階層は、α がBachmann-Howard 順序数であるとき、Wainer 階層における関数f _{ε 0}と同じ増加率を達成することを示した。Girard (1981) はさらに、 α が帰納的定義の任意の有限反復の理論ID _{<ωの順序数であるとき、緩やかな増加階層}g _{α は}(特定の急速増加階層における) f _αと同じ増加率を達成することを示した。(Wainer 1989)

任意の急成長階層の有限レベル（α < ω）における関数は、グジェゴルチク階層の関数と一致する：（ハイパー演算を使用）

• f ₀ ( n ) = n + 1 = 2[1] n − 1
• f ₁ ( n ) = f ₀ ⁿ ( n ) = n + n = 2 n = 2[2] n
• f ₂ ( n ) = f ₁ ⁿ ( n ) = 2 ⁿ · n > 2 ⁿ = 2[3] n ≥ 2の場合
• f _{k +1} ( n ) = f _k ⁿ ( n ) > (2[ k + 1]) ⁿ n ≥ 2[ k + 2] nただしn ≥ 2、k < ω。

_{有限レベルを超えると、ワイナー階層（ω ≤ α ≤ ε 0} ）の関数が存在します。

• f _ω ( n ) = f _n ( n ) > 2[ n + 1] n > 2[ n ]( n + 3) − 3 = A ( n , n )（n ≥ 4）、ここでAはアッカーマン関数（f _ωはその単項バージョン）です。
• f _ω+1 ( n ) = f _ω ⁿ ( n ) ≥ f _{n [ n + 2] n} ( n ) （すべてのn > 0に対して）ここでn [ n + 2] nはn^番目の アッカーマン数です。
• f _ω+1 (64) = f _ω ⁶⁴ (64) >グラハム数（g ₀ = 4、g _{k +1} = 3[ g _k + 2]3で定義される数列のg _{64 ）。これは、} f _ω ( n ) > 2[ n + 1] n > 3[ n ]3 + 2であることに注目すると従い、したがってf _ω ( g _k + 2) > g _{k +1} + 2である。
• f _{ε 0} ( n ) はワイナー階層の中でグッドスタイン関数を支配する最初の関数です。

• Buchholz, W.; Wainer, SS (1987)。「証明可能な計算可能関数と急速に成長する階層」。論理と組合せ論、S. Simpson 編、Contemporary Mathematics、第 65 巻、AMS、179-198 ページ。
• Cichon, EA; Wainer, SS (1983)、「緩慢成長と Grzegorczyk 階層」、The Journal of Symbolic Logic、48 (2): 399–408、doi :10.2307/2273557、ISSN  0022-4812、JSTOR  2273557、MR  0704094、S2CID  1390729
• ガリエ、ジャン H. (1991)、「クラスカルの定理と順序数 Γ ₀の何が特別なのか? 証明理論におけるいくつかの結果の調査」、Ann. Pure Appl. Logic、53 (3): 199–260、doi : 10.1016/0168-0072(91)90022-E、MR  1129778PDF: [1]。(特に第12節、59～64ページ、「急成長関数と緩やかに成長する関数の階層の概要」)
• ジラール、ジャン=イヴ(1981)、「Π ¹ ₂論理。I. ディレーター」、Annals of Mathematical Logic、21 (2): 75–219、doi : 10.1016/0003-4843(81)90016-4、ISSN  0003-4843、MR  0656793
• Löb, MH; Wainer, SS (1970)、「数論的関数の階層」、Arch. Math. Logik、13。訂正、Arch. Math. Logik、14、1971。パート I doi :10.1007/BF01967649、パート 2 doi :10.1007/BF01973616、訂正doi :10.1007/BF01991855。
• Prömel, HJ; Thumser, W.; Voigt, B. 「Ramseyの定理に基づく高速増加関数」、Discrete Mathematics、v.95 n.1-3、p. 341-358、1991年12月 doi :10.1016/0012-365X(91)90346-4。
• Wainer, SS (1989). 「緩やかな成長と急速な成長」. Journal of Symbolic Logic . 54 (2): 608–614. doi :10.2307/2274873. JSTOR  2274873. S2CID  19848720.