第1章 从无有到无穷
在**类弗里德曼宇宙模型中,第四维—时间,正如空间一样,在范围上是有限的。它如一根具有两个端点或边界的线。因此时间具有终结,而且它也有一个开端。事实上,在宇宙具有我们观测到的物质总量的情形下,由爱因斯坦方程得出的所有解中,都有一个非常重要的特征:在过去某一时刻(大约137亿年以前)相邻星系之间的距离必须为零。换言之,整个宇宙被挤压在零尺度的单独一点,就像一个半径为零的球。那时,宇宙的密度和时空曲率都为无限大。它是我们称做大爆炸的时刻。
—摘自史蒂文·霍金《时间简史》
这个零尺度的单独一点被物理学家称做“原点”。它的另一个名字是奇异点(singularity)。但是零尺度是什么意思呢?霍金曾解释过:零尺度就是不占空间。那么不占空间是什么意思呢?也许读者猜出来了:没有(nothing)!即虚无。实际上,物理学家们普遍认为在原点之外没有空间,空间也是大爆炸后的产物。也就是说,宇宙是从无到有的,用希腊文来说就是Ex Nihilo(见图1-1)。
图1-1 Ex Nihilo:宇宙从无到有的一刹那整个宇宙从无到有对一般人来说都很难理解,而这个原点是谁或者如何放在那里也是众���纷纭。不过,这不是本书准备要讨论的问题。本书关心的是算法,而算法具有一个与宇宙起源类似的性质:从无到有。不过这个从无到有却有着非同一般或者说更加丰富的意义,下面将详细分析。
1.1 意念与现实
先看一个例子。给你一个无限容积的罐子和无限个球,球从1开始连续编号。
在差1分钟到零点时:将标号为1~10的10个球放进罐子,然后将10号球从罐子拿出。
在差1/2分钟到零点时:将标号为11~20的10个球放进罐子,然后将20号球从罐子拿出。
在差1/4分钟到零点时:将标号为21~30的10个球放进罐子,然后将30号球从罐子拿出。
……
就这样将游戏进行下去。假定放球和取球不占时间,请问,当时钟指向零点时,罐子里还剩多少个球?
这个答案似乎很直接:无限个球!这是因为所有编号不是10n(n≥1)的球在放进去罐子里后就不会再拿出来;而在零点之前这种放球、取球的次数是无限的。因此,罐子里面的球数在零点时将是无数个。但是你很确信这个答案吗?
现在来让我们改变拿球的方式,将每次拿10、20、30、…号球分别变为拿1、2、3、…号球,即第x次拿球,所拿出来的球的编号是x。结果又会怎样呢?这个时候,神奇的事情发生了。这个罐子里面的球数将为0。我们来看,对于任意一个球,设其编号为n,则在差(1/2)n?1分钟到零点时该球将被取出。也就是说,对于任意球n,在零点时它都不在罐子里。因此,零点时罐子里球的个数为0。对于有些人来说,这个答案似乎不可接受。但又确实找不到驳斥的办法。你能找出来吗?也许这个答案是合理的,因为拿球顺序的变化使得算法发生了变化,即我们实际上讨论的是两个算法。可仔细一想又觉得不对,因为两个算法都是每次放进10个球,拿出1个球,即从根本上说,这是两个一样的算法,怎么会有截然相反的结果呢(见图1-2)图1-2 到底剩多少个球?不同的拿球顺序有不同的结果,如果我们再次改变试验中拿球的方式,将拿某个特定标号的球改为取出任意标号的球,即:
在差1分钟到零点时:将标号为1~10的10个球放进罐子,然后从罐子任意拿出一球。
在差1/2分钟到零点时:将标号为11~20的10个球放进罐子,然后从罐子任意拿出一球。
在差1/4分钟到零点时:将标号为21~30的10个球放进罐子,然后从罐子任意拿出一球。
……
这种拿球方式又将产生何种结果呢?
答案仍然是无有,即0(本书将在第1章对这个问题进行正面解析)。太不可思议了吧!这三个本质相同的算法怎么有如此匪夷所思的结果呢?如果非要说这三个算法有什么不同,那就是拿球时的标号不同。
难道是,标号的不同使*后球的数量发生了变化?
没错。就是这个标号对结果产生了深远影响。从某种意义上说,标号是虚的,它只存在于我们的想象中,但确实对现实结果产生了影响,即我们的思维使算法发生了变化。或许从另一个角度来看,这个问题就是:无有就是无穷,无穷就是无有。它们之间也许根本没有什么不同,它们的不同只存在于人们的想象或者意念中。也许这是为什么无穷的符号(是由两个0连接而成的,从左右两面看都是无有,而从中间看则是无穷,如图1-3所示。
图1-3 无有和无穷的区别也许只存在于人类的思维中从这个意义上说,算法是一种思维方式(algorithmic thinking),或者说一种哲学。而本书就是从算法思维的角度出发,阐述算法的灵魂。
1.2 什么是算法
究竟什么是算法呢?顾名思义,算法就是计算的办法或法则。这里的计算指的当然不只是加、减、乘、除等算术运算,而是广义的做任何事情的计算,而办法和法则意味着使用它就可以解决需要的问题。算法的历史可以追溯到9世纪的古波斯。*初它仅表示“阿拉伯数字的运算法则”。后来,它被赋予更一般的含义,即所谓的一组确定的、有效的、有限的解决问题的步骤。这是算法的*初定义,注意,这个定义里面没有包括“正确”。
推动算法传播的是生活在美索不达美亚的Al Khwarizmi于9世纪一本以阿拉姆语(Aramaic)著述的教科书。该书列举了加、减、乘、除、求平方根和计算圆周率数值的方法。这些步骤的特点是:简单、没有歧义、机械、有效和正确—这就是算法。注意,这个定义加上了“正确”这个词。几百年后,当十进制计数法在欧洲被广泛使用时,“算法”(algorithm)这个单词被人们创造出来以纪念Al Khwarizmi先生。
由上面提到的定义可推知,算法作为解决问题的方法,它必须具备以下特点:
·确定性,即无歧义,能让人照着执行。
·可行性,算法中的运算都是基本的,理论上能够由人用纸和笔完成。
·有限性,在有限输入下,算法必须能在有限步骤内实现有限输出。
此外,算法必须有输出、计算的结果,通常还有至少一个输入量。这是因为算法用以解决的问题的描述均包括输入和输出。