谁能给出更大的数？

2019-03-15  本文已影响0人  raphaelzhang

译文

有这么个老笑话，两个贵族比赛看谁说的数更大。在想了好久之后，第一个贵族得意地宣告说，“八十三！”。第二个则被惊呆了，只好回答说，“你赢了。”

要是参赛者能轮流竞答的话，这种最大数的比赛显然就没有意义了。要是在互不通气的情况下，让参赛者同时写下自己的数呢？我请两位观众志愿者用这种办法来举行比赛，并引入了本文后续关于“大数”的话题。下面就是比赛的规则：

参赛者有十五秒的时间给出一个整数，这个数只能用标准数学符号与字词的组合来表示，但不能是
无穷大这样的词。书写材料是一张空白的索引卡。给的数必须是精确的，任何理性的现代数学家都
应能仅从索引卡与公开文献判定此数的大小。

因此，参赛者不能说“撒哈拉沙漠中沙子的数量”，因为撒哈拉沙漠中沙子的数量在不停地变化。参赛者也不能说“对手的数再加一”，或是“任何人能想到的最大的数再加一”。对于理性的数学家来说，上述说法都太含糊不清了。在上述规则范围内，能给出更大数的参赛者获胜。

准备好了么？预备，开始。

比赛的结果和我想的总是不太一样。有一次，一个七年级的男生在他的纸上写了一串9。他与许多其它的大数新手一样，想在数位上不停地添9让数变得更大。要是他用了写得更快的1，而不是弯弯曲曲的9的话，他的数还会大上百万倍。但就算这样，他也仍然会被其对手女生所击败，她写了一个9，接着在右上角添了一个999。牛啊！一个指数：一个自乘999次的数。看到这个奇想后，我也不去数卡片上有多少个9，立马就宣布女生获胜了。

不过，要是这个女生能把指数堆叠起来的话，她的数还可以再大很多。用9^{9^9}来举个例子，这个庞然大数等于9^{387,420,489}，这是一个369,693,100位数。相比之下，在可观察到的宇宙中所有基本粒子的数量也不过是个约85位的数而已。三个以指数形式堆叠起来的9，就已经比我们能观察到的所有物质的数量还大了，而且要大整整10^{369,693,015}倍，就更别提9^{9^{9^9}}或者9^{9^{9^{9^9}}}了。

数位、指数、堆叠指数，每种形式都可以表现无穷大的数，从这个角度来说，它们都是等价的。但是，不同的符号系统在其能简洁地表现的数上差异极大，这就是限制时间为15秒的意义所在了。写9999，99^{99}与9^{9^{9^9}}的时间是一样的，但是第一个数平平无奇，第二个是天文数字，而第三个则是超天文数字了。最大数比赛的关键不在于看谁写得快，而在于能表现大数的强有力的范式。

这种范式在历史上并不常见。在古代有这么一个时期，在二十世纪也有这么一段时间，在其他时候则波澜不兴。但是，简洁地表现大数的新方法往往是重大科学革命的副产品，这些革命包括系统化的数学体系、形式逻辑，以及计算机科学。而正如科恩派所说，重大的革命只在恰当的社会条件下才能发生。因此，大数的故事同时也是人类前进的历史。

这里还有一个类似的数学故事。在其被低估了的奇书《π的历史》中，彼得.贝克曼（Petr Beckmann）认为圆周长与直径的比值是“一面人类历史的有趣的镜子”。在阿那克萨哥拉与希庇阿斯的古雅典、埃拉托色尼与欧几里得的亚历山大里亚、牛顿与沃利斯所在的十七世纪的英格兰等科学与理性能自如发展的极少数社会环境下，数学家在计算π上都取得了巨大的进步。相形之下，在罗马与中世纪的欧洲，π的发展则停滞了。圆周率被古巴比伦时25/8这个粗糙的估值所代替了。

我认为，这种模式对大数也同样适用。好奇心与开放性既激发了大数的魅力，也让人充满自信，感觉不管多大的数都可以被人类所把握，无论它是宇宙中星辰的数量，还是纸牌可能的排列种数。反过来说，愚昧与理性的缺乏则会导致对大数宿命论的态度。历史学家伊兰瓦迪（Ilan Vardi）引用了古希腊语中的“沙百”（sand-hundred），即口语中的不计其数（zillion）这个词，还有品达在奥林匹克颂II中的一个片段，来说明沙子是不可计数的。

但是，沙子是可以计数的，阿基米德在公元前三世纪就意识到了这一点。下面是他《数沙者》一文的开头，这是一篇给叙拉古国王写的类似科普性质的文章：

有些人……认为沙子的数量是无限的……还有一些人，虽然认为它不是无限的，但认为还没有数
能用来表示如此大的数量……不过，我将尝试向您给出这样的数，它们不仅大于与地球同重的沙子
的数量……而且也大于与宇宙同重的沙子的数量。

阿基米德继续向下推导，他实质上就是用到了古希腊语中的myriad（万）这个词作为基数来表示指数。阿里斯塔克斯提出了一个超越时代的宇宙模型，在其中，固定的恒星所占据的球体要远大于地球围绕太阳旋转的球体，阿基米德以此模型为基础，得到了填充宇宙所需要的沙子数量的上限为10^{63}。（据说，在美语中能用一个单词表示的最大的数即为10^{63}：或说vigintillion。不过vigintillion最好淡定一点，因为还有更异想天开的呢，即表示10^{100}的单词googol，以及表示{10^{{10}^{100}}}的单词googolplex）。虽然这个数很大，但显然10^{63}不可能一直占据第一大数的宝座。六个世纪之后，丢番图发明了一种更简洁的指数表现形式，可以用来表示超过10^{{10}^{{10}^{{10}^{10}}}}的数。当时间跳到中世纪，在阿拉伯数字传入和数位的概念兴起后，堆叠指数就更容易了。但是截止到二十世纪，阿基米德用来表示大数的基本方法仍然没有被超越。时至今日，在有关大数的讨论中，指数仍占据了主导地位。

例如，在那个波斯大臣发明国际象棋的传说中，就用到了指数。国王很喜欢这款新游戏，因此让大臣自己来选择赏赐。大臣说自己是一个谦恭的人，因此他只需要在第一格上放一颗麦粒，第二格两颗，第三格四颗，以此类推，每一格的麦粒数量都是前一格的两倍。数盲国王欣然同意，他没意识到所有64格上的麦粒数一共会有2^{64}-1颗，或约184亿亿颗，相当于今天整个世界150年小麦的产量。

相应地，这种指数级的增长也是国际象棋难度高的原因所在。对于国际象棋的每一步来说，其可选的下法只有约35种，但是当把选择数以指数级连乘起来以后，就衍生出了约10^{50}种棋面布局，就算是电脑也没法把它们穷尽完。这就是为什么直到1997年才诞生了能击败国际象棋冠军的计算机，深蓝。而在围棋中，它的棋盘有19x19个交点，布局超过10^{150}种，连业余棋手都能击败顶级的计算机棋手。在其他方面，指数增长也对计算机造成了极大的困扰。旅行商问题要求在给出每两个城市距离的条件下，求出一条贯穿多个城市中每个城市的最短通路。这里的问题就在于可选的通路数量是随着城市数量的增大呈指数级增长的。例如，有100个城市的时候共有10^{158}条可能的通路，虽然此问题存在一些优化的技巧，但迄今为止，还没有发现比逐一检查每条通路在本质上更好的算法。旅行商问题是NP完全问题中的一个，此类问题包含了上百个具有现实意义的其它问题。（NP是一个术语，即非确定性多项式时间）。现在已知，只要得到了任何一个NP完全问题的高效算法，即可得到所有此类问题的高效算法。在这里，高效指的是算法所花费的时间最多与问题规模的某固定指数项成正比，例如与城市数量的立方成正比。现在普遍猜测，NP完全问题不存在高效算法。此猜想又称P≠NP，对此猜想的证明是计算机科学三十年以来一个悬而未决的重大问题。

尽管计算机可能永远无法高效地解决NP完全问题，但对于计算机科学中的另一个圣杯，即复制人类智能来说，却大有希望。人类大脑有约一千亿个神经元，它们之间通过约一百万亿个突触相互连接。虽然单个神经元的功能现在也只得到了部分理解，但一般认为每个神经元受控发出电脉冲的规则相对比较简单，其频率可以达到每秒一千次。因此，我们可以将其看成是一个内部高度互联的计算机，每秒进行约10^{14}次操作。相比之下，位于桑迪亚国家实验室中，由9200颗奔腾Pro组成的，全球最快的万亿次级并行超算每秒能进行10^{12}次运算。和通常的看法不一样，大脑灰质之网可不只是内嵌了智能，它的性能也比硅片要高。不过，它很快就会丧失这个优势了。其原因就在于摩尔定律，九十年代的摩尔定律指的是硅片上能存储的信息量会指数级增长，约每两年翻一番。当微晶片部件的尺寸达到原子量级，经典光刻技术停滞时，摩尔定律也终将失效。但诸如光脑、DNA计算机，甚至是量子计算机这样全新的技术将替代硅片的位置。计算机的性能不可能永远指数级增长，但是它有足够的时间来超过人脑，至少超过人脑的处理能力。

对于人工智能的预言家来说，摩尔定律是指数级增长的一个伟大胜利。但是指数也有坏的一面。最近全世界人口刚刚超过了60亿，而且大约每四十年就翻一番。要是沿着这种指数增长的速度，假设一个人的平均体重是70公斤，那么到了3750年，整个地球就完全被人类所覆盖了。先别急着投资除体臭剂，在远没有到达这个极限之前人口肯定就停止增长了，其原因可能是饥荒、传染病、全球变暖、大规模种族灭绝、令人窒息的空气，或者让我们来猜猜，是计划生育。因此很容易理解为什么物理学家阿尔伯特·巴特莱特（Albert Bartlett）说“人类最大的缺陷”就是“我们无法理解指数函数”。也能理解为何卡尔·萨根（Carl Sagan）劝诫说“永勿低估指数”。在他《十亿又十亿》这本书中，萨根给出了指数级增长带来的其它恶果。如果每年的通货膨胀率是5%，那么一元钱在二十年后就仅价值37分钱了。如果一个铀原子核发射两个中子，它们又都与其它的铀原子核发生碰撞，使得新的两个原子核每个再发射两个中子，如此递推……嗯，在上面我有没有提到核毁灭也可能是人口增长中断的原因之一？

对于现实世界，还有人们的希望与恐惧来说，指数既常见，又相关，与它们都有着密不可分的联系。在下面我将给出的符号系统中，可以简洁地给出一些大数，使得指数相形见绌，就像9相比999^9相形见绌一样。不过这些新的系统貌似比指数更难懂。在侯世达（Douglas Hofstadter）的《无感于数》一文中，他先将读者们引近了这些系统，接着却说道：

只要我们的讨论再前进一点点，那就会置身于递归函数与算法复杂度的理论之中，而这些都太抽象了。
因此我们不妨就此打住。

可是，就此打住的代价就是放弃，不仅是放弃了最大数比赛，而且也放弃了理解的希望，即理解更强的范式到底是如何处理更大的数的。因此，我们先回到二十世纪早期，在这个时期，有一群被称为形式主义学派的数学家们，他们希望将整个数学奠定在严格的公理体系的基础之上。给“计算”下一个准确的定义，是形式主义学派中最关键的问题之一。换句话说，给定一组数，我们如何判定是否存在一个确定的、机械的方法将其列举出来？部分数学家认为“可计算的”与另一个术语“原始递归”是等效的。但是在1928年，威廉.阿克曼（Wilhelm Ackermann）构造了一组数否证了此命题，这组数显然是可计算的，但它们增长极快，因此不可能是原始递归的。

阿克曼的想法是创建一组无限长的算术运算，每个运算都比前一个更强。第一个运算是加法。第二个是乘法，它可以被看成是连续的加法。比方说，5x3表示5自加了3次，或说是5+5+5=15。第三个是指数运算，它可以被看成是连续的乘法。第四个是……什么呢？好吧，我们只能发明一个新的运算，用来表示连续的指数运算。数学家鲁迪.卢克（Rudy Rucker）称其为迭代幂（tetration）。例如，5对3的迭代幂表示5自乘方了3次，即555，这是一个2185位数。以此类推。第五个就是连续的迭代幂了，我们应该称其为超5运算（pentation）么？第六个就是连续的超5运算了，管它叫超6运算（hexation）？此过程可以无限延续下去，每个运算都比前一个更高更强，直攀入大数的云巅。

要是把每种运算看成是一种糖果的口味的话，我们就可以把阿克曼序列看成一个糖果盒了，可以把每种口味都和一个数混在一起。数列中的第一个数是1+1，或是（别害怕）2。第二个数是2*2，或是4，第三个数是3的3次方，或是27。嗯，这些数也不大么。

嗯 哼 哈 嘿

第四个数是4对4的迭代幂，或说是4^{4^{4^4}}，一个10^{154}位数。要是你想把它写下来的话，最好现在就抓紧时间开写。第五个数是5对5的超5运算，即对5进行5次迭代幂运算。这个数对任何常见的词来说都太大了。从此开始，以后的数会变得愈加巨大。

通过阿克曼序列，我们就可以在最大数的比赛中击败那些没好好听课的对手了。不过我们也要仔细些，因为阿克曼序列有好几个定义，其中有些是不一样的。在十五秒的时间限制之内，我可能会使用下面的式子，以避免歧义：

A(111) 阿克曼数列： A(1) = 1+1，A(2) = 2*2，A(3) = 3^3，……

虽然看起来有点晦涩，但其实阿克曼序列是有用武之地的。在拉姆齐理论的一个问题中要求满足某特定条件下的超立方体的最小维度。一般认为这个数是6，但是迄今为止能证明的最小维度的下界超大无比，因此只能用与阿克曼序列同样奇异的运算来表示。实际上，吉尼斯世界纪录曾将此维度作为在数学证明中使用过的最大的数列入纪录。（参与此项竞争的还有Skewes数，大小约10^{{10}^{{10}^{{10}^3}}}，此数曾经在指数分布的研究中被用到过。著名数学家哈代曾经开玩笑说，Skewes数是“数学中为某具体目标曾用过的最大的数”。）此外，由于阿克曼序列增长极快，它也曾在计算机科学中出现过。例如，在数据结构并查集的研究中，某一项与阿克曼序列的反函数相乘——即对于每个整数X来说，比X大的第N个阿克曼数中最小的N。此反函数增长极慢，正如正函数增长极快类似。在一般情况下，反函数最大也不会超过4。

阿克曼数非常之大，但却仍不够大。如果想要更大的数，我们仍需回到形式主义学派。阿克曼已经证明了“原始递归”并不是我们一般所说的“可计算的”，因此问题还没得到解决：究竟什么是可计算的呢？在1936年，阿隆佐·邱奇（Alonzo Church）与阿兰.图灵（Alan Turing）分别独立地解决了这个问题。邱奇使用的是称为lambda演算的逻辑形式方法，而图灵使用的则是理想化的计算机——图灵机，它在本质上与今天任何一台计算机都是等价的，例如康柏、戴尔、麦金塔与格雷机。图灵的论文名为“论可计算的数”，他在其中描述了上述机器，此文被公认为是计算机科学的奠基之作。

“计算”，图灵说道，

一般是通过在纸上书写特定的符号来进行的。我们可以认为此纸张被划分成了多个方格，正如小朋友的
算术本一样。在小学算术里，有时会用到纸张的二维性。但其实一般并不需要用到二维，而且我想大家
也同意，对计算而言，二维并非必要。因此我假设计算是在一维纸张，即一条被划分为多个方格的纸带
上进行的。

立足于基本原理，图灵通过天才式的推导继续剖析纸带机。他说，纸带是向两侧无限延伸的，因为理论计算机在资源上不应受到现实世界的限定。而且，在每个方格上只能写一个符号，就像现在计算机内存中的0和1一样。不过应该如何操作这些符号呢？好吧，沿着纸带有一个能来回移动的“带头”，在给定规则下，它每次可以读取一个方格上的符号，或者写入符号，或者擦除符号。这些规则就是带头的程序，只要改变了规则，你就改变了带头的行为。

图灵深刻的洞见在于指出通过对带头编程，图灵机可以支持任何计算。图灵机能运算加法、乘法、开立方根、排序、搜索、检查拼写、解析、下三连棋、列举阿克曼数列……如果给它加上键盘作为输入、显示器作为输出，把它们当做符号编码到纸带上，我们甚至可以在图灵机上运行Windows。不过还有一个问题。要是把带头随意放在一串符号上，它可能运行到最后停下来，也可能永不停机。就像故事中的那个程序员一样，看到香波瓶上写着“起泡、漂洗、重复上述步骤”的产品说明后，就陷入了死循环。我们当然希望预先知道图灵机是否会永不停机，这样就不用浪费一辈子去等一个程序的结果了。但是，我们究竟怎样能在有限的时间内判断一件事是否会永远进行下去呢？要是你与朋友打赌，说自己的手表永远不会停下来，那你什么时候能赢呢？不过，也许真的存在某个特天才的程序，它能检查其他的程序，然后能准确地告诉我们，这些程序是否会停机吧。我们只是还没找到这样的程序而已。

绝不可能。图灵证明了，图灵机是不可能解决上述停机问题的。这个证明是一个相当漂亮地使用了自指技巧的例子。它实际上形式化了这样一个论题，那就是为什么你永远不可能认清自己。因为如果你能的话，那你就可以预知10秒之后自己会做什么，到时只要做不同的事就产生了矛盾。图灵假设有这样一个能判断其它程序是否停机的程序，然后他让此程序对其自身进行分析，要是被分析程序永不停机的话就停机，不然就永不停机。这就像一条咬住自己，然后把自己吞掉的猎狗一样，在自相矛盾中，假设的停机判断机就此形影无踪了。（在研究文献里可不能说这种俏皮话。）

棒极了，你可能会说。（也许会说，糟透了）。但是这玩意和大数有什么关系？其实，它们之间的联系直到1962年5月才为人知晓。当时的贝尔实验室技术期刊上，在一批工程气息浓厚的论文，如“多端口结构”、“波导压力密封”等文章的包围中，有一篇不起眼的名为“论不可计算的函数”的论文，作者是蒂柏.雷多（Tibor Rado）。在这篇论文中，雷多引入了超出任何人想象的最大数。

他的想法很简单。就像我们可以把单词按照它们包含的字母数来分类一样，我们同样也可以把图灵机按照其带头包含的规则数来分类。有的图灵机只有一条规则，有的有两条，有的则有三条，如此类推。对某个确定的整数N来说，显然有N个字母的单词的数量是有限的，因此拥有N条规则的图灵机的数量也是有限的。在这些图灵机中，对于空白带来说，有些会停机，有些则永不停机。而在这些停机的图灵机中，雷多进一步问到，最多的能运行到多少步才停机呢？（实际上，雷多问的主要是在停机前最多能写多少个符号。不过最大步数的基本性质也是差不多的，而且推导起来更容易，雷多将其定义为S(n)）。

雷多将此最大值称为第N个“繁忙的海狸鼠”（Busy Beaver）之数，在这里我们称其为BB(N)。接着我们就可以判定任何具有N条规则的图灵机是否能在空白带上停机的问题了。我们可以运行图灵机，要是它停机，那就万事大吉，要是它运行到了BB(N)步还不停机，那我们就知道它肯定永不停机了，因为BB(N)表示的就是有N条规则的图灵机在空白带上运行的最大步数。打个比方，要是你知道凡人都在200岁之前去世，而萨利活到了200，那你就知道萨利是神仙了。因此没有任何图灵机能列举出繁忙的海狸鼠之数，要是它能的话，它就可以解决停机问题了，而我们在上面已经知道这是不可能的了。

不过在这里还有一件有趣的事情。假设我们能给出一个大于BB(N)的数，称为为D吧，代表水坝（dam）的意思，表示它就像水坝一样，挡住下面的海狸鼠。有了D以后，计算BB(N)就简单多了，我们只需要模拟运行所有有N条规则的图灵机就可以了。要是图灵机运行到D步还没有停止，也就是冲过了水坝的图灵机，它们肯定永不停机。这样我们就能准确地知道哪些会停机，进而得到这些在D步前停机的图灵机运行的最大步数，此即为BB(N)了。

结论么？繁忙的海狸鼠之数，即BB(1)、BB(2)，以此类推，它们的增长速度比任何可计算的数列都要快。比指数要快，比堆叠指数要快，比阿克曼数列还要快，你就说吧。这是因为如果有任何图灵机能计算出一个数列，使得其增长速度比BB还要快的话，那我们就可以通过这个图灵机得到D，也就是上面说的水坝数了。而有了D之后，我们就可以列出对应的BB数列了，但是我们在上面已经知道这是不可能的了。（看起来是不是有点眼熟？）BB数列是不可计算的，完全是因为它增长得超级超级快，什么计算机都跟不上它的速度，即使从理论上也跟不上。

这意味着没有任何计算机程序能把BB数列一个个地按序列举出来。但这并不是说任何特定的BB数都不能算出来。实际上，自从雷多发布了他的论文后，把它们一个个找出来已经成了计算机科学界的消遣之一了。很容易就能验证BB(1)，即第一个繁忙的海狸鼠之数，是1。这是因为要是只有一条规则的图灵机要是在第一步都不能停下来的话，那它显然就永不停机了。在此处，不可能有更复杂的行为。如果有两条规则的话，做的事就多一点了，只要费点力气也能弄清，BB(2)是6，即六步。第三个BB数呢？在1965年，雷多和林深（Shen Lin）共同证明了BB(3)是21。这项证明相当艰难，需要人对一系列图灵机进行分析，以证明其永不停机，这是因为，一定要记住呀，没有算法能列举出BB数来。接着，在1983年，艾伦·布雷迪（Allan Brady）证明了BB(4)是107，到此为止也没啥了不起吧？小心，有了阿克曼数列的前车之鉴，可别被开始的数给迷惑了。

在1984年，A.K.杜特尼（Dewdney）在科学美国人上用了一个专栏来介绍繁忙的海狸鼠之数，这件事激发了业余数学家乔治.尤宁（George Uhing）的兴趣，他想开发一个特定的设备用来模拟图灵机。这台设备花费了尤宁不到100美元，找到了一个拥有五条规则，在停机时运行了2,133,492步的图灵机，因此BB(5)至少不低于这个数。然后在1989年，海纳.马克森（Heiner Marxen）和乌尔根.本特洛克（J¨urgen Buntrock）发现BB(5)至少是47,176,870。时至今日，BB(5)仍然没有被最终确定，而且它的值应该会比现在得知的要高得多。至于BB(6)，马克森和本特洛克于1997年创下了新纪录，证明它至少是8,690,333,381,690,951。成就确实惊人，但马克森、本特洛克和其它的BB数狩猎人仍只是在未知领域的边缘徘徊。人类可能永远都无法得知BB(6)的准确数值，更别说是BB(7)或任何后续的数了。

实际上，现在步数最多的BB(5)和BB(6)图灵机已经很晦涩了，我们人类的大脑已经无法理解它们究竟在干什么。要是它们有任何创造力的话，那也肯定不是人类赋予的。理解这件事的一条思路是这样的，即使是很小的图灵机也可能隐含了深刻的数学问题。拿哥德巴赫猜想来举个例子，即任意一个大于或等于4的偶数肯定能表示为两个素数之和：10 = 7 + 3，18 = 13 + 5。自从1742年以来，这个猜想就一直未被证明。但是我们可以设计一个比方说有100条规则的图灵机，用来测试每个偶数，看看它是不是两个素数的和，只有当它找到反例的时候才停机。要是我们知道了BB(100)，那么从理论上来说，我们就可以把这台图灵机运行BB(100)步，看看它究竟是否停机，从而解决哥德巴赫猜想。好吧，我们就此打住，不用继续想这个数列来找死了。

不过雷多强调道，虽然我们不可能列出BB数来，但是它们的数学定义是很明确的。要是你想和朋友进行最大数比赛，我给你建议下面这个答案：

BB(11111)，繁忙的海狸鼠之数，1、6、21……

要是你的朋友对图灵机或类似的事情一无所知，但是只知道比如说阿克曼数列，那你就赢啦。你还可以让一步，给他整个宇宙的时间来写自己的数。最大数比赛的关键是强有力的范式，而图灵的计算理论就确实很强。

但要是你的朋友也知道图灵机呢？是否存在更强大的符号系统，能表示出比BB数还大的数呢？

假设我们赋予一台图灵机以魔力，让它能解决停机问题。我们能得到什么呢？我们可以得到一台超级图灵机，一台比一般的图灵机更强的机器。不过，现在的问题是它是否能判定超级图灵机是否停机呢？嗯……其实超级图灵机也没法解决超级图灵机的停机问题。要解决超级图灵机的停机问题，我们还需要更强的机器，即超超级图灵机。而要解决超超级图灵机的停机问题，我们还需要超超超级图灵机。以此无穷类推。上述无限层级的超级图灵机结构由逻辑学家斯蒂芬·克莱尼（Stephen Kleene）在1943年形式化（虽然他没有用类似超超级图灵机的词）。

假设有这么一部小说，它本身是另一部更长小说的一部分，而这部更长小说则又是一部更更长小说的一部分，如此递推直到无穷。在每一部小说中的人物都可以讨论在其内部嵌套的小说的文学价值，但是他们绝不可能评论他们所在的小说。（我想，这与我们对小说的日常经验是一致的。）要想完全理解某个事实，我们需要置身事实之外才能做到。这就是克莱因层级结构的本质：为了解决某类机器的停机问题，我们就需要更强大的机器。

而这是无法避免的。假设有一台图灵机拥有了解决停机问题的魔力，还能解决超级停机问题，以及超超级停机问题，如此等等，以至无穷。那它肯定是图灵机之王了吧？并非如此，因为一旦我们需要知道图灵机之王是否停机，我们就需要一个更强的图灵机之帝了。克莱因的层次结构就这样继续延续了下去。

这和大数又有什么关系呢？嗯，每层克莱因的结构都会生成一个比之前层次增长更快的BB数列。事实上，每层BB数列的增长都越来越快，只靠更高一层的图灵机才能算出来。比方说，定义BB_2(N)是有N条规则的超级图灵机停机之前能运行的最大步数。如果此超级BB数列能被超级图灵机计算得到，那这些机器就能解决超级停机问题了，但已知这是不可能的。因此超级BB数列增长太快了，超级图灵机只能计算出普通的BB数列来。

你可能会想，在最大数比赛中，你可以使用类似下面的结果击败使用BB数列的对手：

BB2(11111)

但可能并非如此。问题是我从未在任何地方见过这些高阶BB数列的定义，可能是因为对于了解计算理论的人来说，它们是普通BB数列的一个显然的推论吧。所以我们理性的现代数学家就没法理解你到底给出的是什么数了。如果你想在最大数比赛中使用高阶BB数列，我建议你首先得在一个不那么出名，声望较低的期刊上发表一篇论文，对其概念形式化一下。然后再在比赛时在索引卡上引用这篇论文。

要超越高阶BB数，我们就需要比图灵机更强大的计算模型。我很难想象这样的模型会是什么样的。不过我感觉关于大数符号系统的故事可能应该到此为止了。也许有那么一天人类能简洁地给出一个数，它会使得BB(100)也小的可笑，就像我们嘲笑贵族说的83一样。或许我们永远也无法达到这个目标，但是其他的文明可以呢？是否在整个宇宙中都在进行最大数比赛呢？

你可能会奇怪，为什么我们不能超出所有这些范式，使用一个包含一切又超越一切的系统来给出一个数呢？假设你在最大数比赛中写下了下面的文字：

1,000个字以内能给出的最大的整数。

显然这个数是存在的。在1000个字以内，我们能给出的数的数量是有限的，在其中必然有一个最大的。但是我们不知道怎么给出这个数。语言可以阐述阿克曼数列，可以阐述繁忙的海狸鼠之数，或是高阶的BB数，甚至是其它任何人都还没想到过的革命式的概念。所以除非对手也用了类似的手段，比如他肯定就跪了。这想法真不错！我们怎么就没能早点想到它呢？

让人郁闷的是，这个方法并不好使。我们也可以这么写：

1,000个字以内能给出的最大的整数再加一。

这个数显然应该需要用至少1001个字来描述。但是我们刚才只用十七个字就给出了它的描述！就像一条把自己吞掉的蛇，我们的庞然大数在自相矛盾中冰消瓦解了。出了什么问题呢？

我刚才描述的悖论最早是由伯兰特·罗素（Bertrand Russell）发布的，他将此发现归于名为贝利（G.G.Berry）的一名图书管理员。贝利悖论的源头不是数学，而是英文中的歧义。没有绝对稳妥的方法把任意一条短语转换成其描述的数（甚至都无法确定它是否给出了一个数）。这就是为什么我在最大数比赛的规则中引入了“理性的现代数学家”的原因。为了避免贝利悖论，我们需要使用精确的数学符号系统来给出数，比如BB数列背后的图灵机这样的理念。简而言之，没有什么语言上的灵丹妙药能超越阿基米德、阿克曼、图灵与雷多，大数之路没有捷径。

你可能也奇怪为什么我们不能在比赛中使用无穷大。这与我们在自行车比赛中为什么不能使用火箭是同样的道理。无穷大是既有趣又精致的一个概念，但是它并不是一个整数。我们也不能从无穷大中减去一个什么东西来得到一个整数。无穷大减去17仍然是无穷大，而无穷大减去无穷大则是没有定义的，其结果可能是0、38甚至还是无穷大。实际上，存在着不止一个无穷大。在十九世纪末期，格奥尔格·康托（Georg Cantor）证明了无穷大也是分级的，例如一条线上有无穷多个点，这个无穷大要比有无穷多个整数中的无穷大要大。还有一点，正如不存在最大的数一样，也不存在最大的无穷大。对更大的无穷大的研究比对更大的数的研究更困难，不过它不会牵涉到一系列范式，而实质上只涉及一个范式，即康托范式。

到目前为止，我们已经接触到大数的前沿知识了。据说，欧几里得的某弟子曾问到，“这都有什么用呢？”我们已经看到了，大数表现系统的进步也反映了更大范围内的进步，包括数学、逻辑与计算机科学。不过，虽然镜子能反映现实，但却不一定能影响现实。即使在数学里，大数也常常被认为是细枝末节，对它们的研究往往只是一种消遣，而没有什么意义。我想提出一个相反的看法，即对大数的理解是理解世界的关键。

让我们来想象一下如何给阿基米德解释图灵机。这位叙拉古的天才会耐着性子听你讨论向两端无限延伸的莎草纸带、时间分步、状态、输入与输出序列等。最后他还是怒了：

“愚蠢！”，他说（或者用相应的古希腊语说），“你给我的只是一个精巧的定义，在它本身之外没有任何意义”。

你会怎么回应呢？阿基米德从没听说过计算机，这些距离他23个世纪之后难以相处的设备，却渗透到了世界的各个角落。因此你没法说清它有什么实际的用处。你也没法引用希尔伯特（Hilbert）和形式主义纲领，因为阿基米德也没听说过它们。不过这个应该能行：繁忙的海狸鼠之数。你可以给阿基米德定义BB数列，说服他BB(1000)比他能填满整个宇宙的沙子的数量10^{63}还大，比10^{63}的10^{63}次方还要大。只要他不使用图灵机或者类似等效的系统，你就可以在最大数比赛上击败他。在他思考这个问题的时候，图灵机的概念自然就会启发他。虽然他的直觉可能无法理解BB数，但是他的理性却会强迫他承认这些数真的很大。大数可以把抽象的东西变得更具体。

实际上，我们可以把科学看成是理性对我们的补偿，它用来补偿我们无法理解大数的缺陷。要是我们每秒能跑28万公里，那显然就不需要狭义相对论了。因为很明显，我们跑得越快，我们就会变得更重更矮，在其他地方时间的流逝也就更快。要是我们能活七千万年，显然就不需要进化论，也不需要创世论了，我们能亲眼观察到物种的形成与演化，而不用费劲巴拉地从化石和DNA中重构历史事件。要是我们能用两千万度的高温烤面包，核聚变就不再是核物理学家的专利，而会变成日常家务的一部分。但是上面的每件事我们都没法做到，因此我们才有了科学，用它来帮助势单力薄的我们推导出永远无法直观感知到的外物。要是人们害怕大数，那他们也会害怕科学，从而转向小而可思的神秘主义寻求慰藉，这也就毫不奇怪了。

不过，人类害怕大数么？他们当然害怕。我见过不知百万与十亿差异，而且毫不在意的人们。我们投身有六种方法获奖的彩票，却忽略了它还有两千万种方法让你一无所获。我们为每年向大气排放的六十亿吨二氧化碳而叹息，同时又在其指数增长的同时谈论可持续发展。我觉得，这些事情并不只是没有算术常识的问题，而是代表了不愿理解大数的想法。

畏惧大数的心理从何而来？是否有生理上的解释呢？在1999年，由神经心理学家斯坦尼斯拉斯·德阿纳（Stanislas Dehaene）领导的一个研究小组在科学期刊上发表了证据，显示大脑的两个部分与数学思考是相关的。研究小组训练了一群俄英双语实验者，让他们解决一系列的问题，包括两位数的加法、八进制的加法、开立方根、还有对数。某些科目是在俄语下训练的，其它的则是在英语下训练的。当被试者被要求估算问题结果时（从两个选项中选择一个较接近的），他们在两种语言条件下表现得差不多。但是当要求被试者求出精确解时，在其训练时的语言条件下的表现则会更好。此外，脑图扫描显示出，在进行估算时，被试者的顶叶（涉及空间推理）更加活跃。而在精确求解时，被试者的左下额叶（涉及语言推理）则更为活跃。对脑部损伤的患者也有类似的结果，顶叶受伤的患者有时无法判断9到底是与10更接近还是与5更接近，但是却能记住乘法表。而左半脑受伤的患者有时无法判断2+2究竟是3还是4，但是知道其结果与3更接近，比9更遥远。德阿纳等人推测人类使用了两种方式来表示数字。对估算，我们使用了大脑中的数轴，这是经过长期进化而来的，很可能与其它动物是类似的。但是对于精确计算，我们使用的是数学符号，而这是最近才演化出来的，与语言是相关的，仅适用于人类。这个假设可以很清楚地解释实验结果，被试者在精确计算中使用受训语言得到的结果更好，而在估算中两种语言一样的原因是因为前者牵涉到了偏语言的左下额叶，而后者则牵涉到了偏空间的顶叶。

如果德阿纳等人的推测是正确的，那么我们使用大数时用到了哪部分呢？当然是符号部分了，没人能在脑海里想象包含了999，5对5的超5运算，或是BB(1000)这么长的数轴。我觉得这就是问题所在了。在处理3、4、7的时候，我们依赖于经过了数百万年训练的空间直觉，例如3只瞪羚，4个配偶，7个敌对氏族的成员。但是在思考BB(1000)时，我们就只能依赖语言这个进化史上的新生儿了。处理数字的大路变成了死胡同。而这可能就是人们为什么害怕大数的原因。

早期的干预会减轻大数恐惧症么？要是这样呢？二年级老师在繁琐的日常工作中抽出一个小时来，问学生们，“你能怎样给出一个真的、真的超级大数呢？”然后再告诉他们指数、堆叠指数、迭代幂与阿克曼数列，也许还有BB数，一大堆他们从没想到会有这么大数的数，还有超出他们想象的那些理念。

谁能给出更大的数?就是那拥有更强范式的人。你准备好了么？预备。开始！

参考资料

译后记

这是Scott Aaronson于1999年写的一篇文章，今年我碰巧见到，感觉虽然已经时隔20年，但还是蛮有趣而且有意义的，因此联系了作者之后翻译于此。

翻译有信达雅的说法，本文当然相差很远，不过也尽力使得译文不脱离原意，而又能让中国人读起来较为流畅。

由于原文距今已经20年了，因此现状已经有所更新。例如AlphaGo、AlphaZero已经能以大比分击败人类的顶尖围棋大师，例如摩尔定律已被认为失效，还有顶尖超算的算力现在已经超过了十亿亿次，而不是1999年的万亿次，来自中国的太湖之光和天河均是其中的顶尖选手。此外，康柏、麦金塔、格雷机等也已经成为了历史。当然，也有一些东西没有太大的变化，例如大数的进展，例如BB(5)与BB(6)也迄今没有确定，更别说BB(1000)了。

本文当然需要首先感谢Scott Aaronson，其次也欢迎各位给翻译指出问题，及时更正，谢谢。

上一篇下一篇

猜你喜欢

热点阅读