有哪些出名的大数介于G（64）和TREE（3）之间？

发布时间：

2024-05-08 20:24

阅读量：

$1.$ $n(4)$

你可能没有直接听过 $n(4)$ 这个名字，但如果你尝试搜索过 $\mathrm{TREE(3)}$ 有多大的话，很可能就会得到 $A^{A(187196)}(1)$ 的这么一个结果。部分文章会煞有介事地介绍阿克曼函数，并告诉你 $\mathrm{TREE(3)}$ 的下界是 $A^{A(187196)}(1)$ ——实际上这是一个广为流传的谣言。这里的 $A^{A(187196)}(1)$ 根本就不是 $\mathrm{TREE(3)}$ 的下界（或者，更严谨地说，是一个很差很差的下界），而是本段的主角 $n(4)$ 的下界。

$n$ 函数也是一个图论函数，其介绍可以参考https://googology.fandom.com/wiki/Block_subsequence_theorem。目前已证明， $n$ 函数的FGH增长率不低于 $\omega^\omega$ ，但不超过 $\omega^\omega+1$ 。

$2.$ $cg(4)$

$cg$ 函数是一个来源于康威链的函数，定义为 $cg(n)=\underbrace{n\rightarrow n\rightarrow\dots n}_n$ 。如此一来，有 $cg(3)=3→3→3=7625597484987$ , $cg(4)=4→4→4→4$ 则已经远超葛立恒数。 $cg$ 函数的FGH增长率为 $\omega^2$ 。

$3.$ $\mathrm{Hydra}(4)$

$\mathrm{Hydra}$ 函数来源于九头蛇砍树游戏，其介绍可以参考https://zhuanlan.zhihu.com/p/342161307。 $\mathrm{Hydra(4)}$ 的下界为 $f_{\omega\times2+4}(5)$ ，也远超葛立恒数， $\mathrm{Hydra}$ 函数的增长率则为 $\varepsilon_0$ 。顺便一提， $\mathrm{Hydra(5)}$ 的下界是 $f_{\omega^{\omega\times2+4}}(5)$ 。

为什么前三个数的自变量都是 $4$ ？或许只是巧合。这 $cg$ 函数和 $\mathrm{Hydra}$ 在自变量取值为 $3$ 时，函数值都相对较小，未完全迈入大数的领域； $n(3)$ 的下界大于 $G(1)$ ，上界与 $G(2)$ 相当接近，但知名度不如这个讹传的 $n(4)$ 。不过，下面这个就不一样了。

$4.$ $\mathrm{SCG(1)}$ 和 $\mathrm{SCG(2)}$ （未确定）

$\mathrm{SCG}$ 函数是一个著名的图论函数，其介绍可以参考https://www.zhihu.com/question/516473643/answer/2358280357。 $\mathrm{TREE(3)}<\mathrm{SSCG(3)}<\mathrm{SCG(3)}$ 的结论也经常被提及。但是 $\mathrm{SCG(1)}$ 和 $\mathrm{SCG(2)}$ 又如何呢？我们有： $\mathrm{SCG}(1)>f_{\varepsilon_2\times2}(f_{\varepsilon_0\times2}\Tiny{(f_{\varepsilon_0+1}(f_{\varepsilon_0}(f_{\omega^\omega+1}(f_{\omega^5+\omega^2+\omega}(f_{\omega^2\times3+1}(f_{\omega^2\times2+1}(f_{\omega^2+\omega\times3+1}(f_{\omega^2+1}(f_{\omega^2}(3\times2^{118842243771396506390315925504})))))))))}))\\$ $\mathrm{SCG}(2)>f_{\varphi(1@\omega)}(X)\\$ 其中 $X$ 是上面所写的一长串 $\mathrm{SCG(1)}$ 的下界。 $\mathrm{SCG}$ 函数的FGH增长率位于 $\psi(\Omega_\omega\times\omega)$ 和 $\psi(\Omega_\omega^\omega)$ 之间。