信息时代的前尘往事（二）：两千年的接力赛

作者：黄逸文（中国科学院数学与系统科学研究院）

文章来源于科学大院公众号（ID：kexuedayuan）

前传：信息时代的前尘往事（一）：从算盘到计算机

作者按

时光荏苒，沧海横流，变化在加剧，唯一不变的，依然是人们对幸福生活的美好向往。人类文明的进程有时进步，有时停滞，曾经有过古希腊的辉煌，也曾陷入中世纪的黑暗。

正是先贤们对科学的敬畏和追求，终于让我们走出愚昧，在数千年后收获科技的馈赠。当我们有幸品尝到这些丰硕的果实时，理应传颂昔日无数英才们荡气回肠、如泣如诉的往事。

3

两千年的数学接力赛催生现代计算机

1

希尔伯特第十问题 现代计算机的理论源头

图灵奠定了现代计算机的基础，也划定了今天所有计算机的理论极限。

图灵机的诞生看似水到渠成，其背后的核心却是一条蜿蜒流淌了近两千年的思想河流。事实上，图灵是为了解决希尔伯特著名的第十问题而提出有效的计算模型，进而才做出了可计算理论和现代计算机的奠基性工作。希尔伯特问题则可以追溯至古希腊的一位著名数学家。

公元3世纪，古希腊亚历山大城的数学家丢番图主要研究不定方程。不定方程指的是未知数个数多于方程个数的一类代数方程或者方程组。其中一类系数为整数的不定方程，被后世称为丢番图方程。寻找丢番图方程的整数解则开启了代数学上最为辉煌的一个分支。比如著名的费马大定理就是无数丢番图方程的一个极其简单的特例。对于这样一个简单的丢番图方程，后世最杰出的数学家历经358年的不懈探索才最终于1994年由英国数学家怀尔斯解决。

希尔伯特（1862年1月23日—1943年2月14日）

17个世纪后的1900年，德国大数学家希尔伯特在巴黎举办的国际数学家大会上，提出了23个著名的数学问题。其中第十个问题则更是雄心勃勃地对所有丢番图方程发起了挑战。问题的核心是“是否存在一个机械步骤，对任意一个不确定的丢番图方程，都能通过有限步的运算，即可以判定它是否存在整数解？”

2

算法的诞生&计算机的运算极限

希尔伯特第十问题留下了两个悬念。

第一个悬念是科学的“算法”定义。在那个年代，有限的、机械的证明步骤在数学上还没有严格的定义，人们只能凭着感觉去定义这样一种模糊的表达方式。今天我们知道，这样一个问题，本质就是“算法”的概念。

第二个悬念则是问题的答案。如果问题的答案是否定的，那将意味着可能存在着大量数学问题人们永远无法知道其答案是否存在，自然也就无法去找到解决它的办法。人们面对这样的问题只能束手无策。因此一个可以计算的机器可能从诞生之初就有其无法逾越的极限。

到了30年代，图灵和丘奇分别从不同的抽象角度提出了“有效机械算法“的概念。其中图灵提出的图灵机模型倾向于硬件性，且模型直观形象，很快得到了人们的普遍接受。通过图灵机模型，人们第一次理解了“算法”这一基本的深刻概念。也正因为图灵奠定的理论基础，人们才有可能发明改变现代文明的工具：计算机。因此图灵被人们尊称为计算机理论之父。

然而，图灵的立足点不仅于此。为了解决计算机是否存在着理论上的极限这个悬念，让图灵对“计算机”这一概念有了更深的思考。这就是著名的图灵机的停机问题。在图灵眼中，这个问题更加本质和重要。事实上，图灵机正是他为了论证图灵停机问题才顺带提出的模型。

那么，计算机是否真的存在着理论的运算极限呢？这就需要直接回答希尔伯特的第十问题。

二进制

在希尔伯特提出著名的第十问题后，很多杰出的数学家对这一问题投入了大量的时间和精力。功夫不负有心人，70年后，问题终于由前苏联伟大的数学家马季亚谢维奇解决。这深深地震惊了数学界，其影响力也冲击到其他自然和人文科学。人定胜天的理念在那一刻分崩离析。原来世界上存在着无数的数学问题，人们永远不会知道其答案，而且这样的问题远远多于有答案的问题。人类能够认识并解决的问题不过是大自然奥秘中的沧海一粟。因此，计算机先天就存在着理论极限，它严格受制于人类能够解决的问题集合。这无疑也证明了图灵当初的远见卓识。

图灵的证明过程深深地受益于彼时的数学进展。正如当初爱因斯坦为了研究广义相对论，被迫去求助于一套全新的数学工具。幸运的是，广义相对论所需要的所有数学理论基础在1840年即由德国数学家黎曼完成。爱因斯坦为此花费十年时间学习黎曼几何和相关的数学技巧，才最终以一人之力做出了旷世的贡献。

3

康托的无穷集——对图灵的重大启发

图灵的关键想法源自德国数学家康托在19世纪末开创的无穷集合论。然而，这一极具天才创见的理论，在其诞生之初，不但没有给创始人带来应有的荣誉，反而谱写了一段血与泪的科学往事。

两千多年以来，科学家研究的实体都是基于有限的存在，没有人试图踏入无穷的世界。面对这样一个远远超越人类认知的事物，大多数理性的科学家都选择了回避。人们小心翼翼地处理和无穷相关的概念。

自牛顿和莱布尼茨建立了微积分以后，微积分计算的严格性常常被人诟病，迫切地需要数学理论的澄清。到了19世纪，由于分析的严格化和函数论的发展，数学家们对无理数理论、不连续函数理论的研究更是需要理解无穷集合的性质。

时代呼唤着天才。此时，德国数学家康托则独自扛起了挑战无穷的大旗。他以一己之力创造了集合论和超穷数理论。

为了把握和认知无穷的集合，康托创造性地将一一对应和对角线方法运用到集合论的奠基性研究当中。数学的分支虽然众多，但是几乎所有的数学都离不开集合的概念。从某种意义上说，集合就是一切数学的基础。因而如果为集合论奠定了公理化的基础，也就等于为数学奠定了基础。

然而，任何超越时代的贡献都难以在当时被世人承认。康托也为此付出了极其惨重的代价。他的成果遭到同时代数学大师无情地嘲讽。他们组成反康托的联盟，对他进行科学和精神上的双重羞辱。备受打击的康托终于精神崩溃，一度患精神分裂症，最终于1918在德国一家精神病院郁郁而终。

康托（1845年3月3日-1918年1月6日）

历史终究是公平的，遮天蔽日的乌云也无法掩盖天才的光芒。希尔伯特高度赞誉康托的集合论“是数学天才最优秀的作品”，“是人类纯粹智力活动的最高成就之一”，“是这个时代所能夸耀的最巨大的工作”，“谁也无法将我们从康托尔为我们创造的乐园中驱逐出去”。罗素也将其称为“19世纪最伟大的智者之一”的人。

不负所望的是，康托在集合论方面的工作终于将数学置于前所未有的坚固基石之上。19世纪的数学因为他的工作而看到了真正严格化的曙光，由此分析的不严密性问题得到了解决，悬置在数学家心中的一块巨石终于尘埃落定。自康托起，集合论成为数学里最基础和重要的理论分支之一。

让康托意想不到的是，他在研究无穷集合时所发明的对角线方法，则为后世科学家提供了极为本质的灵感源泉。20世纪无数重大的理论成果都受益于此，数学和哲学也因此而焕然一新。比如图灵停机问题、哥德尔不完备定理都是该方法的不同延伸[3]。在这些思想成果的汇聚下，最终造就了今日的信息文明，特别是计算机的发明。

4

罗素悖论

表面上看起来，康托的集合论为数学建立了牢不可破的公理体系大厦。当这座大厦快要完工的时候，事情再次出现了转折。数学的危机不期而至。这次掀起滔天巨浪的是英国数学家罗素。

罗素（1872年—1970年）

罗素悖论彻底粉碎了数学家的梦想。关于罗素悖论的一个通俗版本是：“村子里有一个理发师，他给自己定了一条规矩：‘不给那些所有给自己理发的人理发’。现在就要问，这个理发师该不该给自己理发？”。不管如何回答这个问题，都会导致自相矛盾。这个问题本身似乎就具有不可调和的矛盾。正是因为这种奇怪的逻辑，罗素颠覆了整个数学大厦的基础。

数学是最为严格的科学，然而集合论中居然存在着这样明显而根本的矛盾。为了避免罗素悖论产生的方法，人们开始通过细心地选择数学公理来避免产生罗素的思维怪物，从而重新构建精确唯美的数学体系。1917年，希尔伯特提出来一整套数学纲领。他希望找到一套公理体系能够排除悖论，并挽救精确纯粹而美丽无暇的数学。

希尔伯特希望借助于形式化的手段，抽掉数学证明中的意义，把数学证明抽象成一堆无意义的符号转换，甚至我们人类赖以自豪的逻辑推导，也能表达为一堆符号转换。他试图证明，在任一个无矛盾的形式系统中所能表达的所有陈述都要么能够证明要么能够证伪。在这个系统里不会再出现类似罗素这样的思维怪圈。

5

哥德尔不完备定理——可编程机器问世

然而，14年后的1931年，奥地利裔数学家哥德尔的证明彻底颠覆了希尔伯特形式化数学的宏伟计划。哥德尔的证明揭示出：在任何一个相容的形式化数学理论中,只要它可以在其中定义自然数的概念,就可以在其中找出一个命题，在该系统中既不能证明它为真，也不能证明它为假。通俗地说，就是任何一个数学的公理化体系都不是“完美的”。任何数学公理化系统都需要人为地从外界注入新的公理进去才能让它日趋完善，而它自己并不能完全自动避免矛盾产生。

哥德尔（1906年4月28日—1978年1月14日）

哥德尔定理在数学界掀起了轩然大波，不仅在数学上空前绝后，也蕴含着深刻的哲学意义。它完全改变了人们的世界观，其影响波及到自然科学与人文科学的每一个角落。这一理论的丰碑告诉人们：即使是最“完美”最“纯粹”的数学也都无法保证自身的完全性，更进一步，纯粹完美的世界也并不存在。令人惊异的是，哥德尔证明不完备定理的主要思想以及罗素悖论的方法和康托的对角线法则是一脉相承的[2,3]。更让人意想不到的是，哥德尔在证明中引入了“程序即数据”的理念。这也是现代冯诺依曼式计算机的一个核心思想。可以说，哥德尔不完备定理在冥冥之中即预示了可编程机器的必然问世。

历史的发展总是出乎意料。康托建立集合论是为了给整个数学打下坚实的基础，特别是分析的严格化问题。罗素却在集合论的大厦基石上凿出了一道裂痕，继而引发了数学史上第三次重大的危机。当希尔伯特雄心勃勃地提出形式化猜想时，其目的是为数学证明寻找到一劳永逸的逻辑推理方式，从而避开罗素悖论的陷阱。此时哥德尔不完备定理却彻底粉碎了这份美好的愿望，将数学带入到更深的矛盾之中。奇妙的是，哥德尔在证明中引入的观点却成为后世冯诺依曼式可编程机器的核心理念。

6

计算机的横空出世

在希尔伯特第十问题的启发下，图灵和丘奇分别提出了图灵机和lambda 算子这两个概念。图灵机侧重于将数学概念物理化。它的提出就隐含了实际的物理实现。多年以后，冯·诺依曼遵循其图灵机的概念，据此提出了奠定现代计算机体系结构的冯·诺依曼体系结构。

冯·诺依曼（1903年12月28日-1957年2月8日）

具体而言，最早人们将机器的工作主要放到数学计算上。图灵机解决的正是数学计算的这个焦点问题，他创造了机器指令设计的基本方法。在冯·诺依曼计算机中，一种数学计算已经变成了一条指令。

图灵设计的状态自动转移，就是机器指令的例行程序。这里的指令例行程序设计，就是一条指令执行的一连串机器动作，也被称为有限状态变化。图灵机拥有了自动地实现状态变化的方法。但是，图灵的指令系统因为单一而不够完善。首先，它没能将指令存储起来重复使用。其次，它没能形成实现程序的结构设计。正因为如此，图灵机的应用范围还不够广泛，它无法成为能够处理各种任务的计算机。此后，冯·诺依曼提出的程序数据存储的思想弥补了图灵机的这两点缺陷。目前大多数计算机的体系架构则完全脱胎于冯·诺依曼。尽管如此，冯·诺依曼计算机是改良的图灵机，其基本理念仍然深受图灵机框架的影响。

与此同时，丘奇的lambda 算子则是纯粹数学推理系统的一个形式化。他从纯数学的角度进行抽象，不再关心运算的机械过程而只关心运算的抽象性质。丘奇在几条简洁的公理基础上便建立起了与图灵机完全等价的计算模型，由此奠定了函数式编程语言的基础[3]。

自此，现代计算机所需要的硬件和软件的理论基础已经全部搭建完成，它的诞生是水到渠成，而摩尔定律在制造工艺上保证了计算机能力的指数提升。在经历半个世纪的突飞猛进后，我们终于迎来了移动互联网的时代，同时伴随着大数据、人工智能等等造福人类的技术相继登场。

从丢番图起，人类一直在探索真理的道路上匍匐前行。康托、罗素、希尔伯特、哥德尔、丘奇直到图灵、冯诺依曼、香农等等伟大的名字共同铸就了也许是人类历史上最伟大的发明：计算机。没有谁能单独发明计算机，每一位杰出的科学家都是站在巨人的肩膀上走得更高更远，最终将我们带入了高度发达的信息化时代。

4

计算机将向何处去？

1

非冯诺依曼式计算机

信息时代产生了大量的数据，它所需要的运算能力越来越强。海量数据的分析在航空航天、天气预报、石油勘探、商业运营、金融分析、生物工程等等方面都有了迫切的需求。与此同时，摩尔定律已经触及到了物理的制造极限，传统的冯·诺依曼式计算机也已经渐渐力不从心。只有突破现有的体系结构框架并寻求新的物质介质作为计算机的信息载体，才能使计算机有质的飞跃。科学家们开始努力对冯·诺依曼计算机进行改良，并取得了重大的进展。光子计算机、量子计算机、神经计算机和DNA计算机应运而生。随着超高速计算机的投入使用，我们也会很快迈入全新的信息时代。

量子计算机

但无论是哪种计算机，它们都是图灵机的变形。事实上，图灵早已经发现哥德尔不完备定理在计算理论中有其对应的现象。它揭示了即便是在可以设想出来的性能最好的计算机中，也存在有不可避免的“漏洞”，也存在着大量计算机无法解决的问题。这就是图灵机为现代计算机划定的一条无法逾越的边界。

2

超越图灵

那么，人们是否能造出突破图灵限定的计算机？

这需要回到计算的本质上来看。

早在80多年前，图灵就意识到计算来自于确定性的机械运动。21世纪的电子计算机就是用电子的运动等价于机械运动。图灵猜测人的意识来自于量子力学的测不准原理，而计算是确定的，意识是不定的，因此两者完全不同。图灵机也据此确定了计算机的边界。

突破图灵机的方法之一就是突破确定性的限制，我们就必须要放弃程序的实在性，即需要构造一个每时每刻都在变化的程序。如果一个个体时刻都处在不停的更新中，它的本体不断地随着外界的刺激而改变，那么这个虚幻的个体就有可能超越图灵计算的极限。大自然中恰好存在着这样的实例。比如人脑的信息处理过程就是细胞在不断根据环境的刺激而随时改变，这意味着人体本身可能就是一个超越图灵机的存在。甚至所有的生命体都具有根据环境而改变自己的演化规律。生命体和非生命体的这个区别可能也是图灵机与非图灵机的一个本质差异。

人工智能

随着计算机的能力与日俱增，人工智能的突然爆发也引起了人们的普遍担心。是否有一天人类会被人工智能超越，甚至沦为它们的奴隶成为激烈的争论观点。然而，只要我们回到计算机的本质上来看，一切计算机的本质还是一部图灵机，我们就知道它所具有的极限。正是这种极限让计算机和人有着不可逾越的鸿沟。也因此，当代的计算机设计只能成为人们越来越强大的辅助工具，它能够帮助人们处理确定性的问题，而在计算机的参考下人们亦能做出更加睿智的决策。

5

结语

信息时代，是一个毁灭与重建并存的时代，也是一个机遇与挑战共处的时代。这是一个小人物有幸逆袭的时代，也是一个权威轻易被颠覆的时代，这是一个普通人能够彰显个性的时代，也是一群陌生人可以齐心合作的时代。这个时代的能量与潜力，取决于人们如何更好地利用信息的优势！

参考文献：

[1]《文明之光》，吴军，2014年，人民邮电出版社。

[2]《哥德尔、艾舍尔、巴赫-集异壁之大成》，侯世达著，2013年，商务印书馆。

[3]《暗时间》，刘未鹏，2011年，电子工业出版社。