计算两千年 - 《计算进化史: 改变数学的命运》

生日快乐，我的国

今天介绍的 《计算进化史》只

在翻译组正式成员内进行赠书

, 将好书送与支持 [遇见数学] 的朋友们! 发现数学之美, 传播数学文化, 加入[翻译小组]. 一群喜欢数学的人，欢迎你的加入, 有积分兑换周边或图书, 还有不定期福利哦!  申请链接. 

无论从事何种研究方向的数学家，都该读一读这本书。

这部精巧之作展现了计算在数学中愈发重要的地位，宣告了算法数学时代的来临。这是一段关于“计算”与“数学”故事，散文般生动的文字让读者在阅读中领略数学思想的精粹。

- Bernard Chazell，普林斯顿大学

本文节选自《计算进化史》, 已获图灵许可. [遇见数学]特此感谢!

公理化方法确立之后，人们常常把推理视为解决数学问题的唯一工具。数学家们在自己学科的论述中，几乎不给计算留什么空间。然而，计算却并没有从数学工作中消失——无论在哪个时代，数学家都提出了一些新算法来系统地解决某些类型的问题。数学史有它光彩照人的一面——猜想、定理和证明，也有躲在幕后的一面——计算。

在这一章里，我们将看到数学史中三个重要的时刻。这三个重要时刻分属于不同的时代，启发我们讨论不同的问题。

首先，我们将反思如何解决数学论证与数学实践的明显矛盾——前者几乎没有给计算立足之地，而后者却非常依赖计算。这一矛盾还让我们思考从史前数学到希腊数学的转变是如何发生的。接下来，我们会讨论中世纪数学如何传承了美索不达米亚和古希腊的数学遗产。最后，我们要想一想，为什么古代的几何都是围绕着少数几种几何形状，如三角形、圆、抛物线……而大量的新几何形状——悬链线、旋轮线等都是直到 17 世纪才出现。

欧几里得算法：基于推理的计算

虽然欧几里得的名字与几何和公理化方法紧紧地联系在了一起，但颇为讽刺的是，他的名字也出现在一个用于计算两个自然数的最大公约数的算法——欧几里得算法1中。

1即辗转相除法。——译者注

最初的一种计算两个数的最大公约数的方法，就是挨个用比它们小的数来试除，然后找到那些“正好除尽”的数字，从而确定每个数的约数。比如，要计算 90 和 21 的最大公约数，我们可以先求出 90 的约数（1、2、3、5、6、9、10、15、18、30、45 和 90）和 21 的约数（1、3、7和21），然后只要找到两个列表中同时出现的最大数字，即 3。想要回答诸如“90 和 21 的最大公约数是不是等于 3？”或者“90 和 21 的最大公约数是多少？”的问题，我们根本用不着推理，只需应用上述这个虽然烦琐却条理清晰的算法就行了，它基本上就是把最大公约数的定义简单阐释了一遍。

欧几里得算法可以让我们用不那么烦琐的方式计算两个数的公约数。它的思路是这样的：要计算两个数 a 和 b（比如 90 和 21）的最大公约数，我们可以用较小的数 b 去除较大的数 a。如果“正好除尽”，得到的商是 q，那么 a 就等于 。这时，b 就是 a 的约数，也是 a 和 b 公约数，并且它是最大的，因为对 b 来说，没有比 b 本身更大的约数了。所以 b 就是 a 和 b 的最大公约数。反过来，如果除法“没有除尽”，留下了余数 r，那么 a 就等于 。在这种情况下，a 和 b 的公约数也是 b 和 r的公约数。所以，我们可以用 b 和 r 来代替 a 和 b，它们的最大公约数是一样的。欧几里得算法会反复进行这个计算，直到得到两个做除法时能够“正好除尽”的数，而我们要找的最大公约数就是这两个数中比较小的那一个。如果用欧几里得算法计算 90 和 21 的最大公约数的话，我们会把数对 (90, 21) 换成 (21, 6)，再换成 (6, 3)。由于 6 是 3 的倍数，3 就是我们要的结果。

对于 90 和 21 这两个数来说，欧几里得算法会在进行 3 次除法之后得到结果。更一般来说，无论开始的数字是什么，都可以在有限次计算后得到结果。事实上，在把 a 换成 r 的时候，计算最大公约数的数对越来越小，而递减的自然数数列必然是有限的。

这个例子说明，欧几里得等古希腊人并没有把计算弃置一旁，反而创造出了新的算法。这也展示了推理和计算如何在数学实践中融合起来。和第一个计算最大公约数的算法不同，欧几里得算法的构造要求我们证明几个定理：首先，如果 a 能被 b 除尽，那么 a 和 b 的最大公约数就是 b；其次，如果 r 是 a 除以 b 的余数，那么 a 和 b 的公约数也是 b 和 r 的公约数；再次，除法的余数总是比除数小；最后，递减的自然数数列是有限的。这些结果都建立在推理之上，就像毕达哥拉斯学派证明一个平方数不可能是另一个平方数的两倍一样。

第一个算法的设计不需要推理，但这是个特殊情况。一般来说，仅仅把定义解释一遍是不够的，想要设计出欧几里得算法这样的计算方法需要推理才能完成。

向上滑动阅览简介及目录 

长久以来，推理与证明一直是数学研究不可撼动的基石。然而，从20世纪70代初起，证明方法发生了翻天覆地的变化。伴随着数学领域一个又一个重大突破，人们开始质疑推理的至高地位，重新挖掘计算的价值，试图寻找两者之间的平衡。这一变革将以全新视角解读数学与其他自然科学之间的关系，也为哲学思考照亮不一样的前景。同时，数学与计算机科学之间的关系也随之发生了微妙变化。在所有科学领域中，向来只有数学研究可以不依赖任何硬件设备，全凭人类大脑完成。但是，计算机科学正在挑战这一独特性，努力攻破数学证明的技术难点，将数学研究推向前所未知的疆界。

本书从计算的演变这一独特视角回顾了数学、逻辑学和哲学的历史沿革，展望了计算机科学为数学带来的全新前景，以及由此引发的自然科学与哲学领域的重大变革。

版权声明    阅读    

译者序    阅读    

致辞    阅读    

前言    阅读    

第一篇　古老的起源    阅读    

第 1 章　从史前数学到希腊数学    阅读    

第 2 章　计算两千年    阅读    

第二篇　古典时代    

第 3 章　谓词逻辑    

第 4 章　判定性问题与丘奇定理    

第 5 章　丘奇论题    

第 6 章　为计算树立数学地位的尝试——λ 演算    

第 7 章　构造性    

第 8 章　构造性证明与算法    

第三篇　公理化危机    

第 9 章　直觉主义类型论    

第 10 章　自动化证明    

第 11 章　证明检验    

第 12 章　学界新进展    

第 13 章　工具    

第 14 章　公理的终结？    

结语　旅程的尾声    

附录一　人物简介    

附录二　参考文献    

泰勒斯的定理：数学的发明

算法的设计可能需要推理。回过头来看，这个事实就给美索不达米亚和古埃及的数学带来一个问题：就拿美索不达米亚人来说吧，他们是怎么不靠推理就琢磨出了除法的算法的呢？或许，美索不达米亚人和古埃及人可能有某种暗含的推理方式。和希腊人不同，他们并没有明确地采取推理活动，比方说把推理过程写在泥板上。他们多半并没有意识到推理对于解决抽象数学问题的重要性，但这却并没有影响他们进行推理，就像莫里哀笔下的茹尔丹先生一样，说话如同散文一般却不自知2。

2茹尔丹先生是莫里哀剧作《贵人迷》的主人公，他努力想提高修养，跻身贵族，却闹出许多笑话。——译者注

人们常常强调在设计算法时进行推理的必要性。正因如此，美索不达米亚人和古埃及人虽然没有明确的推理记载，人们却仍然猜测他们进行了推理。然而很少有人指出，正是在这种必要性的启发下，古希腊数学产生了奇迹——从计算到推理的转变。确实，我们可以假设，正是在为设计新算法而进行推理时，古希腊人认识到了推理的重要性。

例如，我们常把“第一个”几何推理归功于泰勒斯。金字塔太高，高度无法直接测量。为了测量它的高度，泰勒斯想到了一个办法：他测量了金字塔在地上的投影长度，再单独测量了一根小木棒的高度和影长，然后应用比例法则。

看起来，泰勒斯的目标是设计一个新算法来计算线段的长度。在构造算法时，他需要证明金字塔和它的投影的比例与木棒及其投影的比例相同。这个定理由此拥有了它内在的价值，也就是我们今天所说的“平行线分线段成比例定理”3。

3本定理亦称“截线定理”。在法语中称为“泰勒斯定理”(Théorème de Thalès)，但汉语和英语中的“泰勒斯定理”常指另一条定理，即直径所对圆周角为直角。——译者注

论证与实践

欧几里得算法的存在还提出了另一个问题，就是数学论证与数学实践的明显矛盾——前者几乎没有给计算立足之地，而后者则非常依赖计算。古希腊人和后来者是怎么一边声称只有推理重要，一边又构造了这些算法的呢？

我们再来看看这个算法是怎么计算 90 和 21 的最大公约数的。一种说法是，我们就是按照算法的说明，“盲目地”把数对 (90,21) 换成了 (21,6)，又换成了 (6,3)，最后得到了 3，这时发现它确实求出了这两个数的最大公约数。换一种说法，我们要说明把数对 (90,21) 换成 (21,6) 是有道理的，证明 90 和 21 的最大公约数等于 21 和 6 的最大公约数。这只需要用到前面说到的一个定理就行了：数 a 与数 b 的最大公约数和 b 与 r 的最大公约数相等，其中 r 是 a 除以 b 的余数。如果用后面这种表述方法，我们就可以完全不提欧几里得算法的事，而只是利用了前面的两个定理，就证明了 90 和 21 的最大公约数是 3。

更具体来说，除了得到结果等于 3 之外，欧几里得算法还构造了一套推理，可以证明 90 和 21 的最大公约数是 3。一旦这个推理完成之后，它是怎么来的就不重要了——只要存在就行了。假如古希腊人及后来者确实认为计算只是构造推理的工具，而且构造“工具”应该隐藏在构造“成果”的背后，那么古希腊数学的矛盾——在数学实践中使用计算，却在数学论证中几乎绝口不提计算——似乎也是情有可原的。

进位制

现在来看看数学史上的第二个时刻吧。我们平常总觉得，如何表示数学对象以及日常生活中的物体，只是个细枝末节的问题。把狮子叫作“狮子”或者把老虎叫作“老虎”并没有什么特别的道理。我们也完全可以另选两个词，只要保证使用完全相同的用法，换个名字也还是一回事。语言学家把这种现象称为符号的“任意性”。同样，我们也完全可以给数字“三”换个词，或者给“3”换个书写符号，也不会有什么大的不同。其他语言本来就用别的词表示数字，比如德语中的“drei”或英语中的“three”，德国人和英国人的数学和我们的数学仍然是一样的。

要是让符号的“任意性”更进一步，我们可能会觉得把数字三十一写成“三十一”“IIIIIIIIIIIIIIIIIIIIIIIIIIIIIII”“XXXI”“3X 1I”还是“31”都没什么区别。然而并不完全是这么回事。

首先，为什么我们觉得需要一种特殊的语言来写数字呢？在科学和其他领域，我们要给用到的对象起名字，但一般来说，这并不需要发明一种特殊的语言。比如，人们给每个化学元素都发明了一个名字：氢、氦……但这还是中文啊。然而化学元素虽多，毕竟是有限的。同样的道理，人们也给每个小的数字都起了一个特殊的名字：“一”“二”“三”……以及一个特殊的符号：“1”“2”“3”……然而数字和化学元素不同，它可是无穷无尽的：给每个数字都起个名字是不可能的，因为一门语言中的符号和单词是有限的。

由此诞生了一种思想：把有限的不同符号组合成无限个符号，用来表示数字。也就是说，不是创造一组词汇，而是发明一套语法——这就是一门语言了。虽然词汇是任意的，但语法的随意性就小得多了，而且对于推理和计算而言，数字语言的某些语法就比别的语法更为实用。在“三十一”“IIIIIIIIIIIIIIIIIIIIIIIIIIIIIII”“XXXI”“3X 1I”和“31”中间，最后一个表示法是最好的：数字“3”表示的是十的个数，而这是通过位置体现出来的。这样，如果把一个数字写在另一个数字下方，个位就对齐个位，十位对齐十位……这样做加减法就会很方便。尤其是做乘法的算法变得简单了——要把数字乘以 10，只要在后面加个 0，也就是把数字向左移一格就可以了。

这种进位制来自于美索不达米亚，其雏形在公元前 2000 年就开始使用了。不过，美索不达米亚人用的体系太复杂，后来印度数学家把它简化了。随后在 9 世纪时，印度体系通过一本叫作《代数学》的书传到了阿拉伯世界。该书的作者是阿尔–花拉子米（al-Khwārizmī），这就是“算法”（algorithm）一词的由来。中世纪的数学家花了几个世纪来完善进位制带来的算法。这套体系在12世纪传到了欧洲。

中世纪的欧洲数学家由此继承了双重的遗产：一面是来自希腊，而另一面又通过进位制吸取了美索不达米亚的数学思想，而后者至少与前者同等重要。

公理化方法的发现并没有扼杀计算。相反，通过继承美索不达米亚的数学遗产，计算的问题一直存在，并成为了中世纪数学家眼中的重要课题。

微积分

在看过了欧几里得算法和四则运算之后，我们现在来看看数学史上的第三个时刻：微积分。微积分是 17 世纪由卡瓦列里、牛顿、莱布尼茨等人共同建立起来的。然而它的根源却可以追溯到古代阿基米德的两个发现：一个是圆的面积，另一个是抛物线弓形的面积。

如今，大家都知道圆的面积等于半径的平方再乘以 。阿基米德还没有得出这一步，但他已经证明圆的面积落在半径的平方的  倍和  倍之间。换句话说，他已经得出了数字  的两位小数。对于抛物线弓形的面积，阿基米德则得出了一个精确解：抛物线弓形的面积等于内接三角形面积的  倍。

为了得到这一结果，阿基米德把抛物线弓形分成了无数个小三角形，然后把它们的面积加起来。

设抛物线内接三角形的面积为单位一，那么根据定义，第一个三角形的面积自然是1。我们可以证明它两侧的两个三角形的总面积是 ，再外侧的四个小三角形的总面积是  ……每组三角形的面积都是前一组三角形的  。于是抛物线弓形的面积就是所有这些三角形的面积总和：，这个无穷数列的和是有限的：。阿基米德可能对给无穷多个数求和还心存疑虑，他就考虑了有限和1、、……也就是抛物线内接多边形的面积，它总是比抛物线弓形本身的面积小。他证明了抛物线弓形的面积不可能小于 ，否则就会小于某个内接多边形了，而这是不可能的。阿基米德还利用外接多边形进行了另一套论证，证明了抛物线弓形的面积不会超过  。如果面积既不能大于  也不能小于 ，那它就只能等于  了。

到了 16 世纪，佛兰德斯数学家西蒙·斯蒂文和法国数学家弗朗索瓦·韦达等数学家开始计算无穷数列求和，那么在推理上就不用兜这么大圈子了。然而，阿基米德的推理就算简化了一点，要证明每组三角形的面积都是前一组面积的  也是要大费周章的。所以，直到 17 世纪，计算几何图形的面积都是件让人伤脑筋的事。

到了 17 世纪，在勒内·笛卡儿发明了坐标表示法之后，人们就顺理成章地用方程来表示曲线了。比如，后面图中的抛物线就可以用方程  来表示。

有了方程，我们就可以想想如何计算抛物线弓形的面积，即曲线与横轴之间部分，而不用把它分解成一堆三角形了。17 世纪数学家们的一大发现，恰恰就是计算曲线围绕的图形面积的方法——只要曲线可以用方程来表示，并且这个方程足够简单。

第一步，找出曲线围成的面积与另一个概念——导数之间的联系。

让我们来考虑一个函数，比如说变量为 x，值为  的函数。这个函数在  处的值是 。简单的代数推理就可以证明，该函数在  处与在 x 处的值之差是  。于是这个函数在 x 和  之间部分的“增长率”就是这个差值除以 h，结果是  。

这个函数在点 x 上的瞬时增长率，也就是在 x 处的“导数”，就是上面这个增长率在 h趋于0时的结果：最后两项消失了，只留下了 。

不过，如果只是为了求函数  的导数，就用不到上面这些推理过程了。实际上，我们可以证明两个函数之和的导数就是其导数之和。我们只需要求出 x 的导数，再求出  的导数，然后加起来就好了。接下来，我们还可以证明函数乘上一个常数之后，其导数也要乘上这个值，所以只需要知道  的导数再乘上 。最后，为了求出 x 和  的导数，只需要知道  的导数是  。那么  的导数就是  。

求  的这两种方法有什么区别呢？对于第一种方法，我们需要进行一个小小的推理，虽然很简单，但也需要动动脑筋。而第二种方法只需应用规则，就可以按部就班地求出导数了：

• 和的导数等于导数之和；

• 常数倍的导数等于导数的常数倍；

•  的导数是  。

一旦证明了这三条规则的正确性，求函数的导数就是一个简单的计算了。这个求导数的方法不是用于数字，而是用于函数表达式。而且，并不是所有的函数表达式都适用，而只适用于能够通过 x 和常数的加法和乘法得出的函数——多项式。更为普适的算法可以处理更丰富的数学语言，比如指数函数、对数函数和三角函数等，不过本质上并没有什么不同。

x 的函数  是函数  的导数。反过来，我们说函数  是  的一个“原函数”。我们可以证明这个函数有好多个原函数，都是在这个原函数上加一个常数得到的。

再回过头来看看求导的规则，构造出一套求原函数的规则也不难：

• 和的原函数等于原函数之和；

• 常数倍的原函数等于原函数的常数倍；

•  的原函数是  。

一步步应用这个算法，我们就可以求出  的一个原函数： 。

让我们回到求面积的问题上。微积分的基本定理把面积和原函数的概念联系了起来。如果设  是横坐标为 x 的竖线左侧的抛物线部分的面积，由于函数  是连续的，不难证明函数 F 的导数就恰好是  。

换句话说，函数 F 是  的一个原函数：它是  加上一个常数。由于在  时 F 的值是 0，这个常数值就只能是 ，那么 F 就是  。抛物线形的面积就是这个函数在 1 处的值，即  。我们得到了和阿基米德一样的结果，不过用的方法却不是把抛物线弓形拆成小三角。如果想求曲线  围成的抛物线弓形的面积，就用不着构造一套复杂的推理来求拆分出来的这些小三角的面积了——只要用前面说的方法求出  的原函数，然后调整常数，满足 -1 处的值是 0，再取 1 处的值就可以了。

与求导算法一样，这个算法也只能用于多项式。更普适的算法确实可以处理更复杂的数学语言，不过推广起来不像求导算法那么方便。在三个多世纪的时间里，求原函数的过程一直混杂着算法与技巧，并需要一定的熟练度，一会儿偏计算，一会儿偏推理。直到 20 世纪开发了形式计算程序，积分算法理论才形成体系。我们后面还会讲到它。

回到 17 世纪，随着导数和原函数概念的出现，以及相应算法的建立，许多求面积，甚至求体积、长度、重心……的问题都被简化为简单的计算。一类问题的解法系统化了，求解起来容易了，人们就可以探索更广阔的数学世界。古代的数学家已经求出了某些图形的面积，而 17 世纪的数学家走得要远得多。要求出某些复杂曲线，比如  在 -1 和 1 之间围成的面积，古代数学家会头疼不已，然而对于 17 世纪的数学家来说就是小菜一碟：只要计算  的一个在 -1 处等于 0 的原函数（），再取原函数在 1 处的值，就得到了结果： 。这些算法工具让我们能够对付那些在“赤手空拳”时看似难比登天的问题。没有这些工具时无法研究的一些新几何图形也在 17 世纪出现了。

算法方法融入了几何学这一公理化方法的“圣殿”，在这一数学分支的名称中留下了深刻的印记：我们谈到它的时候不会说“积分理论”，而是说“微积分”。在英语里，“calculus”一词就专指这一数学分支，而另一个词“computation”指的则是一般的计算。(本章完)