“有限与无限”系列 · 上篇
有些数大到无法写完，有些数大到无法用普通指数描述，还有些数之所以巨大，并不是因为它们堆叠了更多的零，而是因为它们来自组合结构、递归过程与可计算性的边界。
人类很早就开始给大数命名。万、亿、兆、京、垓、秭、穰、沟、涧、正、载，已经足以覆盖日常生活与绝大多数科学计数。佛教典籍中还出现极、恒河沙、阿僧祇、那由他、不可思议、无量大数等名称。不同典籍和时代对这些数名的具体进位规则并不完全一致，但无论采用哪一种传统，它们在现代大数理论面前都仍只是有限数世界里相对温和的一角。
真正有趣的问题不是“还能再加多少个零”，而是：我们能否发明一种有限的语言，准确指向一个远远大于任何可实际书写数字的整数？
一、古戈尔：宇宙中的粒子也不够用二、指数塔：重复乘法已经不够用了三、几个曾震撼公众的著名大数1. 斯奎斯数：从解析数论中诞生2. 莫泽数：五边形里的递归3. 葛立恒数：曾进入吉尼斯纪录的证明上界四、TREE(3)：葛立恒数只是它脚下的尘埃TREE(3) 与葛立恒数谁更大？五、SCG(13)：简单图游戏中的又一次爆炸六、Busy Beaver：增长快到任何算法都追不上七、拉约数：比拼的不是增长，而是语言能表达什么八、为什么不存在最大的有限数？九、再大的有限数，也没有碰到无限参考资料
一、古戈尔：宇宙中的粒子也不够用
1920 年代，美国数学家爱德华·卡斯纳请年幼的侄子米尔顿·西罗塔为 起名。孩子给出的名字是 googol，中文通常译作“古戈尔”。
它就是 1 后面跟 100 个零。这个数虽然巨大，却仍可完整写在一张纸上。它的重要性不在于数学结构有多复杂，而在于它第一次以一个生动名字提醒公众：数学中的数可以远远超过物理世界中可计数对象的数量。
可观测宇宙中的粒子数常被粗略估计在 数量级附近。即使这个估计只用于直觉比较，也足以说明：我们无法拿宇宙中的每个粒子去对应古戈尔中的每一个单位。
随后出现的是 古戈尔普勒克斯：
它是 1 后面跟一个古戈尔个零。不要把它误解为 ；指数运算从右往左结合， 比 大得不可同日而语。
如果每秒写十亿个零，从宇宙诞生一直写到今天，也远远写不完一个古戈尔普勒克斯。于是我们第一次遇到大数理论的核心事实：
数字本身无法展开，不妨碍它被精确定义。
二、指数塔：重复乘法已经不够用了
加法是重复计数，乘法是重复加法，乘方是重复乘法。若继续重复乘方，就得到幂塔。
例如：
这里的 4 表示幂塔高度，而不是指数前的乘数。只增加一层，规模就会发生远超普通指数增长的跃迁。
为了压缩这种结构，唐纳德·克努特提出了上箭头记号（以下采用递归定义，避免公式渲染歧义）：
双箭头表示幂塔（tetration）；为避免展开式在不同渲染器中产生歧义，以下面的递归定义为准：
三箭头则表示重复进行双箭头运算，可递归定义为
箭头数量每增加一个，增长层级都会发生质变。
例如：
即使这个数已经极其庞大，它与后文中的葛立恒数相比仍只是起跑线附近的一粒尘埃。
类似的压缩记号还包括康威链式箭号、超运算、斯坦豪斯—莫泽记号等。大数记号的意义并不是制造视觉奇观，而是把“不断重复某种增长操作”变成一个可递归定义、可严格推理的数学对象。
三、几个曾震撼公众的著名大数
1. 斯奎斯数：从解析数论中诞生
斯奎斯数与素数计数函数 和对数积分 的比较有关。早期结果给出了一个极其巨大的上界，用来保证两条函数曲线最终会出现交叉。
在假设黎曼猜想成立时，斯奎斯最初得到的上界常被写作大约
不假设黎曼猜想时，早期上界还要更大。后来这个上界被大幅改进，所以“斯奎斯数”更适合被理解为大数史上的标志：一个严肃的数论问题，曾自然产生出远超日常想象的数值上界。
2. 莫泽数：五边形里的递归
斯坦豪斯提出用几何图形表示大数：把 放入三角形表示 ，放入正方形表示重复 次三角形操作，放入圆形则继续重复正方形操作。
莫泽把这个体系向外推进，并定义了著名的莫泽数。它远远超过古戈尔普勒克斯，也超过大多数仅靠固定高度幂塔构造的数字。
莫泽数的启示是：真正的大数往往来自递归定义的操作次数本身也由巨大数字控制。
3. 葛立恒数：曾进入吉尼斯纪录的证明上界
葛立恒数来自拉姆齐理论中的一个高维超立方体染色问题。它并不是为了争夺“最大数字”而编造出来的，而是一个数学证明中得到的有限上界。
先定义
接着递归定义
最后令
这就是通常所说的葛立恒数。
注意它的恐怖之处：第二步中的箭头数量不是 4、100 或古戈尔，而是前一步产生的整个巨大数字 。仅仅 就已无法用通常幂塔直观展开；从 迭代到 ，增长层级不断自我放大。
尽管如此，葛立恒数仍是一个普通的有限整数。它有确定的个位数，事实上也可以借助模运算求出末尾若干位。巨大并不等于模糊。
四、TREE(3)：葛立恒数只是它脚下的尘埃
如果只知道一个著名大数，很多人会想到葛立恒数；但在现代大数文化中，TREE(3) 才是更具冲击力的名字。
TREE 函数来自图论与克鲁斯卡尔树定理。我们考虑带有有限颜色标记的有限根树，并构造一个序列，要求第 棵树至多有 个顶点，同时任何较早的树都不能以保持结构与标记的方式嵌入较晚的树。
定义为使用 种标记时，这类坏序列能够达到的最大长度。
前两个值小得出奇：
然而
却发生了难以想象的爆炸。它不仅大于葛立恒数，而且大到克努特上箭头、康威链式箭号等常见记号若不引入更高层递归，也很难给出有意义的尺度比较。
这种突变揭示了组合数学中的一种深层现象：
- 局部规则非常简单；
- 对象只是有限的树；
- 问题只问一个最长序列；
- 但“避免嵌入”的全局约束会制造出超乎想象的有限长度。
TREE(3) 的巨大，不来自故意堆叠指数，而来自一个自然组合定理背后的序结构。
TREE(3) 与葛立恒数谁更大？
结论非常明确：
这里的 不是严格运算符，只是强调二者差距巨大。把葛立恒数乘方、做幂塔、甚至进行许多层熟悉的快速增长操作，仍不足以逼近 TREE(3) 所处的层级。
五、SCG(13)：简单图游戏中的又一次爆炸
哈维·弗里德曼研究有限图与有限形式系统时提出过若干快速增长函数，其中常被大数爱好者提及的是 SCG(13)。
SCG 可粗略理解为某类“带标签子立方图序列”的最大长度问题：每一步只能使用受限规模的有限图，同时要求早先图不能嵌入后来的图。它与 TREE 函数一样，把一个看似朴素的有限组合限制推到极端。
SCG(13) 通常被认为远大于 TREE(3)。但这里需要保持严谨：不同资料可能采用略有差异的函数定义与记号约定，因此比较时必须确认双方使用的是同一版本。
它再次说明，大数排行榜不是一条靠多写几个箭头就能统一排列的直线。不同大数往往来自不同的形式系统、序数分析和组合原理；真正的比较需要把它们翻译进共同的增长层级。
六、Busy Beaver：增长快到任何算法都追不上
前面的数虽然巨大，却仍可由明确递归规则计算，至少原则上如此。忙碌海狸函数则把我们带到可计算性的边界。
考虑只有 个非停机状态的图灵机。让这些机器从空白纸带开始运行，并只考察最终会停机的机器。定义：
- ：所有这类停机机器中，停机前写出最多数量的 1；
- ：所有这类停机机器中，运行步数最多者的步数。
因为候选机器数量有限，最大值一定存在。但不存在一个算法能对任意 都正确计算 Busy Beaver 函数；否则便可据此解决停机问题。
这意味着 Busy Beaver 最终会超过每一个可计算函数。无论你设计怎样疯狂的递归、幂塔或箭头系统，只要它仍对应一个可计算函数，Busy Beaver 在足够大的输入处终将把它甩在身后。
这里必须区分两件事：
- 每个具体的 都是有限整数；
- 整个函数却不可计算。
大数由此从“写不下”升级为“没有统一算法算得出”。
七、拉约数：比拼的不是增长，而是语言能表达什么
2007 年，MIT 举行了一场“大数决斗”。规则不是无限制地说“对方的数字加一”，而是要求参与者用有限符号和规定语言定义一个自然数。
阿古斯丁·拉约最终给出的思想，可简化为：
取一个最小自然数，使它大于所有能够用不超过一个古戈尔个符号、在指定集合论语言中唯一描述的有限自然数。
这便产生了通常所称的拉约数。
拉约数的威力来自元语言：它不再逐层构造一个大数，而是把某个形式语言在长度限制内能够描述的所有数字一次性收集起来，然后跳到它们之上。
不过，“拉约数是最大的数”是错误说法。任何有限数 都有 。拉约数只是在指定语言、指定符号预算与指定语义规则下，压过所有可在该限制内定义的数。改变语言或增加符号预算，又可以定义更大的数。
八、为什么不存在最大的有限数？
无论一个数多大，只要它是有限整数，就可以加一：
因此不存在“最大的自然数”。所谓著名大数，通常属于以下几类：
- 文化命名型：古戈尔、古戈尔普勒克斯；
- 记号构造型：幂塔、莫泽数；
- 数学问题上界型：斯奎斯数、葛立恒数；
- 有限组合极值型：TREE(3)、SCG(13)；
- 可计算性边界型：Busy Beaver；
- 语言支配型：拉约数。
它们不是按“零的数量”排成一列，而是代表了人类制造和理解大数的不同方法。
九、再大的有限数，也没有碰到无限
设 是古戈尔普勒克斯、葛立恒数、TREE(3)、拉约数，或者任何别的有限整数。集合
仍然只有有限个元素。只要从 1 开始逐个计数，总会在有限步后结束。
自然数集合
则不存在最后一个元素。它不是“数到了某个极大的终点”，而是根本没有终点。
所以：
这里并不是说二者与 很接近。恰恰相反，有限与无限之间没有一条通过不断变大便能跨越的数值坡道。所有有限整数，无论多大，在最小的无限基数面前都属于同一个有限阵营。
下一篇将正式进入无限：为什么自然数和偶数一样多？为什么实数比自然数更多？为什么无限不止一种大小？以及为什么不存在最大的无限？
参考资料
- Agustín Rayo, Big Number Duel
- Stanford Encyclopedia of Philosophy, Infinity
- Harvey Friedman 关于有限组合陈述与巨大有限数的相关研究
- Ronald Graham 与 Bruce Rothschild 关于拉姆齐理论及相关上界的研究
- Author:阿尔法
- URL:https://yjy.hauchet.cn/article/large-numbers-googol-graham-tree3
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!
Relate Posts
