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

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

定义

编辑

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

  •  
  •  
  •   ,如果 α 是极限序数。

这里,fαn(n)=fα(fα(...(fα(n))...)) 为函数fαn为起点的第n迭代;α[n] 表示将基本序列的第n个元素分配给极限序数α。

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

该层级的初始部分由索引为有限序数(即 α<ω)的函数fα组成,通常称为Grzegorczyk阶层,因为它与Grzegorczyk 阶层密切相关。但请注意,前者是函数fn的索引族,而后者是函数的索引族 

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

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

Wainer 阶层

编辑

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

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

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

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

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

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

急成长阶层的函数

编辑

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

  • f0(n)=n+1=2[1]n−1
  • f1(n)=f0n(n)=n+n=2n=2[2]n
  • 对于n≥2,f2(n)=f1n(n)=2n·n>2n=2[3]n
  • 对于n≥2,k<ω,fk+1(n)=fkn(n)>(2[k+1])nn≥2[k+2]n

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

  • 对于n≥4,fω(n)=fn(n)>2[n+1]n>2[n](n+3)−3=A(n,n) ,其中A阿克曼函数fω是其一元版本。
  • 对于所有n>0,fω+1(n)=fωn(n)≥fn[n+2]n(n) ,其中n[n+2]n第 n阿克曼数
  • fω+1(64)=fω64(64)>葛立恒数=由g0=4,gk+1=3[gk+2]3 定义的序列中的g64。由此可知fω(n)>2[n+1]n>3[n]3+2,因此fω(gk+2)>gk+1+2。
  • fε0(n) 是 Wainer 阶层的第一个增长率超过所有Goodstein 函数的函数。

参见

编辑

大数

缓成长阶层

参考

编辑
  1. ^ Beklemishev, L.D. Proof-theoretic analysis by iterated reflection. Archive for Mathematical Logic. 2003, 42 (6): 515–552 [2024-03-14]. S2CID 10454755. doi:10.1007/s00153-002-0158-7. (原始内容存档于2023-05-13). 

来源

编辑