急成长阶层

在可计算性理论、计算复杂性理论和证明理论中，急成长阶层（也称为扩展Grzegorczyk阶层或Schwichtenberg-Wainer阶层） 是一类定义域和值域为自然数集，以序数作为索引的函数，即急成长函数f_α: N → N构成的集合（其中N是自然数集 {0, 1, ...}，并且索引 α 的范围可达某个大的可数序数）。例如：Wainer阶层，或Löb–Wainer阶层是所有具有索引 α<ε₀ 的急成长函数。

急成长阶层提供了一种根据增长率和计算复杂性对可计算函数进行分类的自然方法。

定义

令 μ 为一个大的可数序数，使得对于每个极限序数α<μ，都存在一个基本序列（一个严格递增的序数序列，其上界为α），属于急成长阶层的函数f _α : N → N ，对于 α<μ，定义如下：

• $f_{0}(n)=n+1,$
• $f_{\alpha +1}(n)=f_{\alpha }^{n}(n)$
• $f_{\alpha }(n)=f_{\alpha [n]}(n)$ ，如果 α 是极限序数。

这里，f_αⁿ(n)=f_α(f_α(...(f_α(n))...)) 为函数f_α以n为起点的第n次迭代；α[n] 表示将基本序列的第n个元素分配给极限序数α。

另一种定义将函数的迭代次数设为n+1，而不是上面第二行中的n。

该层级的初始部分由索引为有限序数（即 α<ω）的函数f_α组成，通常称为Grzegorczyk阶层，因为它与Grzegorczyk 阶层密切相关。但请注意，前者是函数f_n的索引族，而后者是函数集的索引族${\mathcal {E}}^{n}$ 。

进一步推广上述定义，通过将f₀取为任意定义域和值域为自然数集的非减函数 g: N → N来获得急成长阶层。对于不大于ε₀的极限序数，基本序列有一个简单的自然定义（参见Wainer阶层）。但超过ε₀时，定义要复杂得多，然而，急成长阶层的定义可能远远超出 Feferman-Schütte 序数Γ₀ ，至少达到Bachmann-Howard 序数。使用Buchholz psi 函数，可以将急成长阶层的定义扩展到超限迭代的序数$\Pi _{1}^{1}$ -理解（参见层次分析）。

完全确定的超出递归序数的扩展被认为不可能；例如，Prӧmel 等人。 [1991]（第 17 页） 348）指出，在这种尝试中“问题甚至会出现于序数表示法中”。

Wainer 阶层

Wainer阶层是通过定义基本序列获得的函数f_α (α≤ε₀ ) 的特定快速增长层级，如下所示：[Gallier 1991][Prӧmel, et al., 1991]：

对于极限序数 λ<ε₀ ，以康托范式表示，

• 如果 λ=ω^α₁+...+ω^α_k−1+ω^α_k 对于α₁≥...≥α_k−1≥α_k，则 λ[n]=ω^α₁+...+ω^α_k−1+ω^α_k[n],
• 如果 λ=ω^α+1，则 λ[n]=ω^αn，
• 如果 λ=ω^α ，α为极限序数，则 λ[n]=ω^α[n]，

• 如果 λ=ε₀，则取 λ[0]=0 且 λ[n+1]=ω^λ[n]如 [Gallier 1991] 中所述；或者，采用相同的序列，除了以 λ[0]=1 开始，如 [Prӧmel, et al., 1991] 中所示。
  对于n>0，有些版本在生成的指数塔中具有一个附加 ω，即 λ[n]=ω^ω⋰ω，具有n 个ω，或 λ[n]=ω↑↑ω。

一些作者使用略有不同的定义，例如，ω^α+1[n]=ω^α(n+1)，而不是 ω^αn；

有些作者仅针对 α<ε₀定义此层次结构，因此将f_ε0及以上的函数排除在外。

对于索引超出 ε₀ 的函数，请参阅维勃伦层次结构的基本序列。

急成长阶层的函数

任何属于急成长阶层的有限索引 (α<ω) 函数与 Grzegorczyk阶层的函数一致：（参见超运算）

• f₀(n)=n+1=2[1]n−1
• f₁(n)=f₀ⁿ(n)=n+n=2n=2[2]n
• 对于n≥2，f₂(n)=f₁ⁿ(n)=2ⁿ·n>2ⁿ=2[3]n
• 对于n≥2，k<ω，f_k+1(n)=f_kⁿ(n)>(2[k+1])ⁿn≥2[k+2]n 。

超出有限索引的函数 (ω≤α≤ε₀) 参见Wainer阶层：

• 对于n≥4，f_ω(n)=f_n(n)>2[n+1]n>2[n](n+3)−3=A(n,n) ，其中A是阿克曼函数，f_ω是其一元版本。
• 对于所有n>0，f_ω+1(n)=f_ωⁿ(n)≥f_n[n+2]n(n) ，其中n[n+2]n是第 n个阿克曼数。
• f_ω+1(64)=f_ω⁶⁴(64)>葛立恒数=由g₀=4,g_k+1=3[g_k+2]3 定义的序列中的g₆₄。由此可知f_ω(n)>2[n+1]n>3[n]3+2，因此f_ω(g_k+2)>g_k+1+2。
• f_ε0(n) 是 Wainer 阶层的第一个增长率超过所有Goodstein 函数的函数。

参见

大数

缓成长阶层

来源

• Buchholz, W.; Wainer, S.S (1987). "Provably Computable Functions and the Fast Growing Hierarchy". Logic and Combinatorics, edited by S. Simpson, Contemporary Mathematics, Vol. 65, AMS, 179-198.
• Cichon, E. A.; Wainer, S. S., The slow-growing and the Grzegorczyk hierarchies, The Journal of Symbolic Logic, 1983, 48 (2): 399–408, ISSN 0022-4812, JSTOR 2273557, MR 0704094, S2CID 1390729, doi:10.2307/2273557 
• Gallier, Jean H., What's so special about Kruskal's theorem and the ordinal Γ₀? A survey of some results in proof theory, Ann. Pure Appl. Logic, 1991, 53 (3): 199–260, MR 1129778, doi:10.1016/0168-0072(91)90022-E   PDF: [1] （页面存档备份，存于互联网档案馆）. (In particular Section 12, pp. 59–64, "A Glimpse at Hierarchies of Fast and Slow Growing Functions".)
• Girard, Jean-Yves, Π¹₂-logic. I. Dilators, Annals of Mathematical Logic, 1981, 21 (2): 75–219, ISSN 0003-4843, MR 0656793, doi:10.1016/0003-4843(81)90016-4  
• Löb, M.H.; Wainer, S.S. (1970), "Hierarchies of number theoretic functions", Arch. Math. Logik, 13. Correction, Arch. Math. Logik, 14, 1971. Part I doi:10.1007/BF01967649, Part 2 doi:10.1007/BF01973616, Corrections doi:10.1007/BF01991855.
• Prömel, H. J.; Thumser, W.; Voigt, B. "Fast growing functions based on Ramsey theorems", Discrete Mathematics, v.95 n.1-3, p. 341-358, December 1991 doi:10.1016/0012-365X(91)90346-4.
• Wainer, S.S. Slow Growing Versus Fast Growing. Journal of Symbolic Logic. 1989, 54 (2): 608–614. JSTOR 2274873. S2CID 19848720. doi:10.2307/2274873.