在可计算性理论、计算复杂性理论和证明理论中，缓成长阶层是缓成长函数gα: N → N的序数索引族（其中N是自然数集合, {0, 1, ... }）。缓成长阶层的增长率与急成长阶层形成鲜明对比。
定义
令 μ 为一个大的可数序数，以便将基本序列分配给每个小于 μ 的极限序数。函数gα: N → N的缓成长阶层（对于α g_0(n) = 0
- g_{\alpha+1}(n) = g_\alpha(n) + 1
- 对于极限序数α， g_\alpha(n) = g_{\alpha[n]}(n)。
这里， α[n] 表示分配给极限序数 α 的基本序列的第n个元素。
关于急成长阶层的文章描述了所有 α0 的基本序列的标准化选择。
例
- g_1(n) = 1
- g_m(n) = m
- g_\omega(n) = n
- g_{\omega+m}(n) = n+m
- g_{\omega m}(n) = mn
- g_{\omega^m}(n) = n^m
- g_{\omega^\omega}(n) = n^n
- g_{\varepsilon _0}(n) = n\uparrow\uparrow n
与急成长阶层的关系
对于较小的索引，缓成长阶层比急成长阶层增长得慢得多。即使gε0也只相当于f3，并且当α达到巴赫曼-霍华德序数时，gα也只能达到fε0的增长率。皮亚诺算术无法证明偏函数结构中的第一个函数。
然而与之形成鲜明对比的是，吉拉德证明，缓成长阶层最终会赶上急成长阶层。具体来说，存在一个序数α使得对于所有整数n
: gα(n)α(n)α(n+1)
其中fα是急成长阶层中的函数。他进一步表明，第一个使之成立的α，是归纳定义的任意有限迭代的理论ID的序数。然而，对于中发现的基本序列的分配，第一次匹配发生在ε0级别。对于Buchholz风格的树序数，可以证明第一次匹配甚至发生在\omega^2 。
将证明的结果扩展到相当大的序数表明，低于超限迭代序数的序数非常少\Pi^1_1 -理解缓成长阶层和急成长阶层相匹配的情况。
缓成长阶层极其敏感地依赖于底层基本序列的选择。
参考
- PDF's: [ftp://ftp.cis.upenn.edu/pub/papers/gallier/kruskal1.pdf part 1] [ftp://ftp.cis.upenn.edu/pub/papers/gallier/kruskal2.pdf 2] [ftp://ftp.cis.upenn.edu/pub/papers/gallier/kruskal3.pdf 3]. (In particular part 3, Section 12, pp. 59–64, "A Glimpse at Hierarchies of Fast and Slow Growing Functions".)
笔记
评论 (0)