关于满足G(2↑↑n) > TREE(3)的n值的技术问询
G(2↑↑n) > TREE(3)的n值的技术问询 TREE(3)是一个大到需要用序数算术才能证明其有限性的极端大数。我一直好奇:要取多大的n才能让G(n) > TREE(3)? 这里的G(n)是Goodstein序列的长度——也就是从n开始生成序列直到到达0所经历的数字个数。证明所有n对应的G(n)都是有限的同样需要序数算术,而我对Goodstein序列更为熟悉。
已知的Goodstein序列相关结论
- 当
n≥8时,需要用一个递减的ω^ω+1序数序列来描述Goodstein序列,且G(12)已经大于葛立恒数。 - 当
n≥16时,序列需要从ω^ω^ω迭代开始,这样的大数就算用葛立恒数级别的迭代都难以想象。 G(65536)则需要ω↑↑4级别的迭代。
我的核心问题是:要取多大的n,才能让G(2↑↑n) > TREE(3)? 我选择2↑↑n这种表示法,是因为如果直接用G(n) > TREE(3),n的取值可能会大到离谱。
我自己做了一些调研,找到了关于TREE(3)大小的专业讨论,里面给出了TREE(3)的下界,不过我还在消化这些内容。如果能给出一个下界形式的部分答案,我也会非常感激!另外我还找到了一个关于Kruskal弱树函数下界的相关讨论,结合维基百科上的TREE(3)条目,或许能为这个问题的下界提供线索。
补充编辑:通过快速增长层级(Fast-growing hierarchy)以及另一个关于Tree(n)的专业讨论,我找到了一个可能的答案方向。先把Goodstein序列用快速增长层级精确表示出来(希望我的符号是正确的):
G(4) = f₃(3) - 2G(8) = f_{ω+1}(3) - 2G(16) = f_{ω^ω}(3) - 2G(2↑↑n) = f_{ω↑↑(n-1)}(3) - 2
另外,关于TREE(3)的讨论中给出了这样的不等式:
TREE(3) ≥ H_{ϑ(Ω^ω, 0)}(n(4))
我知道快速增长层级可以用Hardy的H函数来表示,但我不太理解不等式里的Ω^ω符号。看起来这意味着需要更多层的对角化,甚至有可能无论n取多大(哪怕是能写出来的数),TREE(3)都大于G(2↑↑n)?
备注:内容来源于stack exchange,提问作者Sheldon L

