小谈大数

简介

计算机科学是关于计算的科学,它最开始要做的事情就是定义了什么是计算,就像牛顿定义了什么是力,香农定义了什么是信息一样(虽然这些定义和直觉可能不太一样)。在明确了什么是计算之后,计算机科学就可以区分说什么是可计算的,什么是不可计算的,而在可计算的部分中,又进一步划分出了什么是容易计算的,什么是难以计算的,从而提出了P vs. NP的数学难题。

既然是计算,当然只有大数的计算才有点意思,不然我们直接手算都行,还用得着什么计算机科学。这篇文章就是聊一下关于大数的问题的,不过需要预先声明的是,我们也是站在巨人肩膀上的,我们主要参考的是伽莫夫的《从一到无穷大》与Scott Aaronson的《谁能给出更大的数》,后者的译文摘录当然已经得到了译者的允许了。

大数

在《从一到无穷大》这本书中,两个原始人比赛谁说的数更大,第一个绞尽脑汁想出了一个大数“3”,另一个苦思冥想之后仍束手无策,只好甘拜下风。古罗马人用I表示1,V表示5,X表示10,C表示100,D表示500,M表示1000,因此如果要表示十万,那就需要连续写100个M,可见大数在古代确实是很少见,而且很难想象的。这里还有一个例子,古希腊语还有一个类似“沙百”(sand-hundred)的词来表示无穷多,说的就是沙子的数量实在太多,是数都数不完的。不过,伟大的后古希腊数学家阿基米德显然对此表示不服,他定义了一系列新的数字单位,计算出了塞满整个宇宙所需要的沙子的数量,答案大约是10的63次方,顺便说一句,英语里还真有一个词叫vigintillion的,正好表示10的63次方。当然,相对于googol(没错,就是google的正确拼法)来说,它还小了10的37次方倍。

话说回来,我们在上面列举的数当然很大,这就是我们常说的指数式增长。如果你和别人比赛看谁写的数大,那显然,在都只能写三个9的情况下,$9^{9^9}$最大,$9^{99}$次之,$99^9$第三大,最小的也就是最常见的999了。具体一点,第一个是个369693100位数,第二个是95位数,第三个是18位数,第四个就只是3位数了。

也许,舍罕王,也就是那个传说中发明国际象棋的宰相所侍奉的国王对指数式增长最熟悉了,第一格只放一颗麦子,第二个放两颗,以后每一格里的麦子数都是前一格的两倍……直到第六十四格,或者说,合计约184亿亿颗麦粒。若一个麦粒重0.02克,则总重也超过了千亿吨。怪不得国王要发疯,这个宰相简直在对数盲国王狂开嘲讽啊。

超越指数

那么,是否有比指数级更大的数呢?

当然是有的。在数学家给“计算”下定义的过程中,一部分数学家提出了一套递归函数的定义,并认为所有的可计算函数都是递归函数。而数学家阿克曼则举了一个反例,他设计了一个明显可计算的阿克曼函数,但是此函数却不符合递归函数的定义,从而迫使数学家们放弃了之前的想法。下面就是阿克曼函数A(m, n)的定义:

  • 当m=0时,A(m, n)=n+1
  • 当n=0时,A(m, n)=A(m-1,1)
  • 其它时,A(m, n) = A(m-1, A(m, n-1))

显然,m是迭代运算的次数,n是具体的数,我们来尝试计算下A(0, n), A(1, n), … , A(4, n)。

按递归条件可知:

  • A(0,n) = n+1
  • A(1, n) = A(0, A(1, n-1)) = 1+A(1,n-1) = … = n+A(1, 0) = n+A(0,1) = n+2
  • A(2,n) = A(1, A(2,n-1)) = A(2, n-1)+2 = … = A(2, 0)+2n = A(1,1)+2n = 2n+3
  • A(3,n) = A(2, A(3, n-1))=2A(3, n-1)+3 = … = $2^nA(3, 0) + 3 (2^n-1)=2^{n+3}-3$
  • A(4, n) = A(3, A(4, n-1))=$2^{A(4, n-1)+3}-3= … =2^{2^{2^{.^{.^{.}}}}}-3$

其中最后一个叠加指数中包括底数一共有n+3个2,将n=2分别代入上式,可以得到3, 4, 7, 29和$2^{65536}-3$,最后一个数太大了,一共有一万九千多位,肯定会让编辑恨死我的。

可见阿克曼函数实际上是一个函数序列,序列中的每个函数都是前一个函数的更高次运算,从加法到乘法,再到指数运算,再到叠加指数运算……所以,阿克曼函数序列的增长是非常快的。

而且,在计算机科学中,阿克曼函数确实被用到了,在常见的并查集经典算法的时间复杂度分析中,可以求得对应算法的时间复杂度为$O(n\alpha(n))$,其中的$\alpha(n)$即为阿克曼函数的反函数。

顺便说一句,数学家们最后确定了,可计算的函数可以以多种等价的方式来定义,包括哥德尔提出的递归可枚举函数,丘奇的λ运算,以及众所周知的图灵机。

超越图灵

阿克曼函数序列中靠后的函数都是大魔王级别的,增长率远超过指数函数,但是毫无疑问,它仍然是可计算范围内的函数。要想比阿克曼函数更大,那不妨尝试一下超越可计算函数,或者说超越图灵机。

那究竟应该找一个怎样的函数,使得其既定义清晰,又不可计算呢?

在1962年,贝尔实验室的雷多(Rado)发表了一篇论文,定义了一个叫做繁忙的海狸鼠(Busy Beaver)的函数,可以达到上面两个目标。对于有n条指令的一定会停机的图灵机T(i)来说,如果它最多运行X(i)步就会停机,而显然有n条指令的一定会停机的图灵机的数量是有限的,因此在这些X(i)中,必然存在一个最大值,将其定义为BB(n)(Busy Beaver,繁忙的海狸鼠)即可。

显然BB(n)的定义是很清楚的,我们来看为什么BB(n)是不可计算的。首先需要回忆一下,经典的停机问题已经告诉大家,世界上没有通用的方法来判断任意一台图灵机(也就是一个程序)是否会永不停机(也就是死循环)。因此,如果我们知道了图灵机的指令数n和对应的BB(n),就可以让这台图灵机最多运行BB(n)步,如果它在此期间停机了,那这台图灵机是可停机的,不然这台图灵机将永不停机。因此,BB(n)显然是不可计算的,不然停机问题就是可解的了。

我们来试试海狸鼠之数是多少,BB(1)显然是1,BB(2), BB(3), BB(4)分别是6、21和107,看起来都好小。但是迄今为止,人们都没有找到或者证明BB(5)是多少,只不过可以通过尝试,确认它不小于47,176,870,而同样通过尝试,我们知道BB(6)至少不小于8,690,333,381,690,951。

除了卖萌,BB(n)还会有什么实际的用处呢?我们可以写一个程序用来验证哥德巴赫猜想,它不停地枚举大于2的偶数,将其分解为两个质数之和,直到找到一个无法分解的偶数才停机。那么,如果这个程序一共含有100条指令,我们只要知道了BB(100),那么就可以运行这个程序BB(100)步,如果它到那时还不停机,我们就知道它永远不会停机了,也就是说哥德巴赫猜想肯定成立。

大数之用

说了半天大数,好像都是数字游戏。实际上,我们可以把科学看成是一种补偿,它可以帮助我们理解大数。要是我们每秒能跑28万公里,那显然就不需要狭义相对论了。因为在奔跑过程中跑得越快,我们就会变得更重更矮,在其他地方时间的流逝也就更快。要是能活七千万年,我们显然就不需要进化论,也不需要创世论了,我们能亲眼观察到物种的形成与演化,而不用费劲巴拉地从化石和DNA中重构历史事件。要是能用两千万度的高温烤面包,核聚变就不再是什么高精尖黑科技,而会变成每天厨房做饭的一部分。但是上面的每件事我们都没法做到,因此我们才有了科学,用它来帮助我们推导出永远无法直观感知到的外物。要是人们不喜欢大数,那他们也很可能会不喜欢科学。

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

如果德阿纳等人的推测是正确的,那么我们使用大数时用到了哪部分呢?当然是符号部分了,没人能在脑海里想象包含了$9^{9^9}$,五阶阿克曼函数,或是BB(1000)这么长的数轴。在处理3、4、7的时候,我们依赖于经过了数百万年训练的空间直觉,例如3只瞪羚,4个配偶,7个部落死敌。但是在思考BB(1000)时,我们就只能依赖语言这个进化史上的新生儿了。处理数字的大路变成了死胡同。而这可能就是人们为什么害怕大数的原因。

发表评论

电子邮件地址不会被公开。 必填项已用*标注