那些很大的数

· · 学习·文化课

大家还记得 xyix.github.io 是一个发表学术文章的网站吗。不用问也知道你们肯定是记不得了。

在 b 站刷到了某些排列大数吓人的视频和在贴吧刷到汪峰在吧的叉义叉非常生气，决定来介绍一下正确的叠盒子方式。

今天我们来介绍一下那些很大的数，以及那些增长很快的函数（当然，代个值进去就是很大的数了），以及我们表示它们的方法 Fast-Growing Hierarchy（暂译：函数增速等级）。

从葛立恒数开始

虽然知乎上的网友天天挑战葛立恒数失败而遭人嘲笑，但其实它的构造并不复杂。

想要构造很大的数怎么办呢！当然是先打个 1 然后一直按住你键盘上的 0 了！也就是幂函数。

我们首先记

a\uparrow b=a^b 记 $$ a\uparrow\uparrow b=a\uparrow(a\uparrow (\ldots)) $$ （一共 $b$ 个 $\uparrow$） 以此类推，$\uparrow\uparrow\uparrow$ 就是打 $b$ 个 $\uparrow\uparrow$，$\uparrow\uparrow\uparrow\uparrow$ 就是打 $b$ 个 $\uparrow\uparrow\uparrow$。~~（汪峰在吧吧友最讨厌的叠盒子时间。）~~ 记 $$ g_1=3\uparrow\uparrow\uparrow\uparrow 3 $$ 那么 $g_2$ 是什么呢？并不是继续叠 $3\uparrow^{(5)} 3$ 这种无聊的盒子，而是更为劲爆的 $$ g_2=3\uparrow^{(g_1)}3 $$ 以此类推，$g_{64}$ 就是我们的葛立恒数。 ## 盒子的等级 从刚才的例子我们很明显可以看出盒子之间也有等级之分。下面我们介绍 FGH，一种衡量它的方法。 令 $$ f_0(n)=n+1 $$ $$ f_{k+1}(n)=f^{(n)}_k(n) $$ 看起来还是一种很无聊的叠盒子方式！连葛立恒数都衡量不了！（遇到 $g_1\rightarrow g_2$ 的 $f_2(n)=g^{(f_1(n))}(n)$ 式叠盒子方式直接投降了。） 那是因为我们需要： ## ~~超单体~~超限序数的盒子 根据我们上面的等级，$\uparrow^{(k)}$ 对应 $f_{k+2}$，也就是 $k+2$ 级别。为了叠上面那个更猛的盒子，我们实际上就是在考虑 $\uparrow^{(n)}$，领悟一下的话，它的增长速度实际上是全体 $\uparrow^{(k)}$ 的上确界，也就是，$\omega$ 级别！ （阿克曼函数大约就在这个位置。） 如果 $\alpha$ 是一个超限序数，令 $$ f_{\alpha}(n)=f_{\alpha[n]}(n) $$ 其中 $\alpha[n]$ 是 $\alpha$ 所对应的**基本序列**的 $n$ 号元素。（下标从 $0$ 开始） 基本序列这个概念很难有一个准确的解释，但也很直观，下面我们会通过一些例子来说明。 比如： - $\omega[n]=n$。嗯，$f_{\omega}(n)=f_n(n)$，很符合我们把它造出来的目的。（也就是说，$\omega$ 的基本序列是 $\{0,1,2,3,\ldots\}$，很符合直觉。） - 按照前面的规则，$\omega+1$ 应当是 $\omega$ 叠一层盒子，即 $f_{\omega+1}(n)=f_{\omega}^{(n)}(n)$。 - （葛立恒函数 $g(n)$ 大约就在这个位置。） 把 $\omega$ 也多叠几次会怎么样呢？ - $f_{\omega+\omega}(n)=f_{\omega+n}(n)$。 - （事实上，对于 $\alpha=\omega^{i_1}+\omega^{i_2}+\ldots+\omega^{i_k}$，$\alpha[n]=\omega^{i_1}+\omega^{i_2}+\ldots+\omega^{i_k}[n]$。） 那让我们直接快进到乘方吧。 - $\omega^{k+1}[n]=\omega^{k}\cdot n$。也就是 $f_{\omega^k}(n)=f_{\omega^k\cdot n}(n)$。（$\omega^{k+1}$ 的基本序列是 $0,\omega^k,\omega^k\cdot 2,\omega^k\cdot 3,\ldots$，很符合直觉。） - （康威链式符号大约就在 $\omega^2$ 的位置。如果允许把一长串箭头连写成 $\rightarrow_n$，它大概就在 $\omega^3$ 的位置。） - $\omega^\omega[n]=\omega^{\omega[n]}=\omega^n$。也就是 $f_{\omega^{\omega}}(n)=f_{\omega^n}(n)$。 继续乘方没有意义。我们直接快进到乘方的极限 $\varepsilon_0$（$\omega^x=x$ 的第一个不动点，或者 $\omega^{\omega^{\omega^{\ldots}}}$。如果你不知道请先了解序数理论。） - $\varepsilon_0[n]=\omega\uparrow\uparrow n$。也就是 $f_{\varepsilon_0}(n)=f_{\omega\uparrow\uparrow n}(n)$。（也就是说，$\varepsilon_0$ 的基本序列是 $\{1,\omega,\omega^\omega,\omega^{\omega^{\omega}},\ldots\}$。） - （著名的 Goodstein 数列（那个九头蛇问题）大约就在这个等级。） - （据说皮亚诺公理体系到这个增长率会崩坏，使得 $f_{\varepsilon_0}(n)$ 无法被证明在每一个 $n$ 处都有定义。你需要 ZFC。） 所以，我们知道，叠有限大数的盒子就是在叠超限序数的盒子。那么让我们进入下一个层级 ## Veblen 等级 既然知道了还有 $\varepsilon_0$ 这种“第一个不动点”的叠法，那么我们把它拓展一下。 令 $\phi_0(\alpha)=\omega^{\alpha}$。它的第一个不动点就是我们的 $\varepsilon_0$。 接下来让我们寻找“下一个”不动点。我们知道 $\varepsilon_0$ 怎么乘方都只能得到它自己，所以我们把它 $+1$ 再不断乘方，得到序列 $\{\varepsilon_0+1,\omega^{\varepsilon_0+1},\omega^{\omega^{\varepsilon_0+1}}\,\ldots\}$，这样当然会有一个极限，也就是 $\phi_0$ 的第二个不动点 $\varepsilon_1$。 令 $\phi_1(\alpha)$ 是 $\phi_0$ 的第 $\alpha$ 个不动点。（$\varepsilon_0$ 算第 $0$ 个）以此类推。 自然，我们可以用同样的方法叠出 $\phi_0(\omega),\phi_{\omega}(0),\phi_{\varepsilon_0}(0),\phi_{\phi_{\phi_{\ldots}(0)}(0)}(0)$ 等等盒子。第三个，也就是上述寻找不动点的过程的极限，被记为 $\Gamma_0$，是 $\phi_{\alpha}(0)=\alpha$ 的第一个解。 ---- 下面我们考虑定义它们的基本序列。 很显然随着我们之前叠过的盒子越来越多，叠盒子的方式也越来越花，分类讨论也不可避免地越来越复杂了。不过好在这些叠盒子方式都是我们以前见过的，不必担忧。 不妨先考虑 $0,1,2,\ldots,\omega+1$ 这种不是极限序数（极限序数不是任何序数的后继，比如 $\omega$ 就是第一个极限序数）的情况。 令 $\phi_0(\alpha+1)[n]=\omega^{\alpha}\cdot n$。这符合我们之前的定义。 - 对于 $\phi_{\beta+1}(0)$，令其基本序列为 $\{0,\phi_\beta(0),\phi_\beta^{(2)}(0),\ldots\}$。 - 对于 $\phi_{\beta+1}(\alpha+1)$，令其基本序列为 $\{\phi_{\beta}(\alpha)+1,\phi_{\beta}(\phi_{\beta}(\alpha)+1),\phi^{(2)}_{\beta}(\phi_{\beta}(\alpha)+1),\ldots\}$。 也就说，正好是我们上述的找不动点的“过程”。 - 而对于极限序数 $\beta$， - 如果 $\beta<\phi_{\beta}(0)$： - - $\phi_\beta(0)[n]=\phi_{\beta[n]}(0)$。 - $\phi_{\beta}(\alpha+1)[n]=\phi_{\beta[n]}(\phi_{\beta}(\alpha)+1)$。这对我们来说应该是很熟悉的叠盒子方式了。 - 否则（比如 $\beta=\Gamma_0,\Gamma_1,\ldots$），直接投降，我们需要另一种形式来表示它们的基本序列。 而如果 $\alpha$ 是极限序数，那么 $\phi_{\beta}(\alpha)[n]=\phi_{\beta}(\alpha[n])$，不论 $\beta$。 --- 对于 $\Gamma_{\beta}$ 的情况需要特判。 - $\Gamma_0$ 的基本序列为 $\{0,\phi_{0}(0),\phi_{\phi_0(0)}(0),\ldots\}$。 - $\Gamma_{\beta+1}$ 的基本序列为 $\{\Gamma_\beta+1,\phi_{\Gamma_{\beta}+1}(0),\phi_{\phi_{\Gamma_{\beta}+1}(0)}(0),\ldots\}$。 - 如果 $\beta$ 是一个极限序数，那么 $\Gamma_{\beta}[n]=\Gamma_{\beta[n]}$。 ---- 大功告成！ 现在让我们看看我们已经到哪里了： - "Friedman's TREE function dominates $f_{\Gamma_0}$ in a fast-growing hierarchy described by Gallier (1991)."（wiki） 草。 ## 非递归 那么就继续叠吧！然后你就会遇到 $\text{SVO},\text{LVO},\text{BHO},\text{TFB}$ 等等无聊的东西。反正都是叠盒子。 那么有没有叠盒子叠不出来的东西呢？序数的世界里当然是有的。把所有这些可以递归构造的数打包成一个集合，就成了一个新的不可"递归构造"的数，我们称其为 $\omega_1^{\text{CK}}$。 "递归构造"也可以称为"超算术"，熟悉图灵机计算理论的观众应该不会陌生。想要找到 $\omega_1^{\text{CK}}$ 对应的增长速度，也只能放弃递归函数的思路直接从那些超越图灵机能力的问题入手。 定义 $\Sigma(n)$ 是“有 $n$ 个状态，读写头只能在一条全白纸带上移动，图灵机可以把纸带上的格子在黑白间转换，而且能停机”的所有图灵机中，能访问最多的格子者所访问的格子数量。而 $\text{BB}(n)$（是的没错就是 Busy Beaver 的缩写）则是最大所用步数。 $\Sigma(n)$ 和 $\text{BB}(n)$ 都是不可计算的数列，我们无法用图灵机对任意给定 $n$ 都保证能算出 $\Sigma(n),\text{BB}(n)$，因为那会涉及到停机问题。 事实上，$\Sigma$ 和 $\text{BB}$ 恰好是 $f_{\omega_{1}^{\text{CK}}}$ 级别。咱也不知道为什么。 --- 或许你已经注意到 $\omega_{\color{red}1}^{\text{CK}}$ 下面的 $\color{red}1$ 了。那是因为我们可以在允许使用 $\omega_1^{\text{CK}}$ 和超算术的情况下再构造出一个集合，称其为 $\omega_2^{\text{CK}}$，一个不能用 $\omega_1^{\text{CK}}$ 加递归构造构造出的数。 它当然也有数列与它对应。仍是考虑 Busy Beaver 问题，但我们让这台图灵机获得神谕机（$\omega_1^{\text{CK}}$）的帮助。 具体来说，是免费给 Beaver 三个特殊状态“询问”“是”“否”，当图灵机进入询问状态，神谕机会数出黑格子的数量 $x$，然后运行所有图灵机（图灵机的数目显然是可数的）中的 $x$ 号图灵机。因为神谕机的强大能力，它可以解决图灵机的停机问题。如果这台虚拟图灵机停机了，就会把 Beaver 设为状态“是”，否则设为“否”。 如此，在这个问题下我们定义 $\Sigma_2(n)$ 和 $\text{BB}_2(n)$。它们恰好是 $f_{\omega_2^{\text{CK}}}$ 级别。 ~~新的盒子已经出现~~ --- 还有另一类能导出更大的不可计算数的问题，叫做 **I**nfinte **T**ime **T**uring **M**achine。 如果在任何自然数时间 $t$ 下 Beaver 都不停机，那么令每个格子在 $t=\omega$ 下的颜色为该格子在各时间颜色（$0$ 为白，$1$ 为黑）的**上极限**，读写头移到初始位置，状态被设为一个特殊状态“极限”。Beaver 这时继续运行，如果 $t=\omega+n$ 时仍不停机就来到 $t=\omega\cdot 2$。 最终，如果 Beaver 在 $t=\alpha$ 停机，一个格子为黑当且仅当 $\forall \beta<\alpha$ 总 $\exists \beta<\gamma<\alpha$，使得 $\gamma$ 时该格子为黑。 定义 $\Sigma_{\infin}(n)$ 是 $n$ 个状态下能在某个序数 $\alpha$ 下停机且能使输出形如 $11\ldots100\ldots$ 的所有图灵机中，$1$ 的数量最大者。结果是，$\Sigma_{\infin}$ 最终大于所有可以被 ITTM 计算的函数。 *或许还有后续……* 参考资料： [1] [Fast-growing hierarchy](https://en.wikipedia.org/wiki/Fast-growing_hierarchy) 及其关联页面, Wikipedia。 [2] [大数入门](https://www.docin.com/p-2128722751.html), 知乎用户 Hypcos。（这位的知乎号还真关注一些修仙文相关话题，乐。）（Googology Wiki 点名批评，原作者也承认错漏较多，请谨慎参考。） [3] [Googology Wiki](https://googology.fandom.com/wiki/Googology_Wiki), Googology Wiki。 [4] [A Zoo of Ordinals](http://www.madore.org/~david/math/ordinal-zoo.pdf), David A. Madore。