智慧的疆界 从图灵机到人工智能

信息科学在 20 世纪 40 年代的开场可以说是一个完美的开局，在接下来的数十年内，信息科学和信息技术产业的发展也是一帆风顺的，在计算机、通信、互联网等方面取得了丰硕的成果。但在人工智能这个领域，信息科学的发展却几经波折，三起两落。虽然现在有了 ChatGPT、Stable Diffusion 等语言和图像生成式模型，有了 Siri、Cortana 等人工智能助理，也有像 DeepBlue、AlphaGo 人机大战等人工智能的新闻和事件，但相比人类对人工智能的最初期望，甚至相比计算机、互联网这类直接地、革命性地改变人们工作和生活方式的科技成果，信息科学在人工智能领域所取得的成绩只能说是差强人意，没有完全达到最初的设想。为何信息科学在人工智能领域的进展不如预期，甚至在几段特定的时间里完全陷入了“泥潭”？让机器拥有智能这个事情到底有多难？人类精英们做了怎样的努力和探索尝试？目前人工智能领域到底发展到了什么阶段？这些都是笔者希望在本书中与大家一同探讨的问题。

1.3 图灵机：计算的基石

英国数学家、密码学家阿兰·图灵（Alan Turing，1912—1954，人工智能之父），这位被一些英国的学者和媒体评价为“未开一枪，却胜百万雄兵”“在二战期间间接拯救了上千万人生命”的传奇学者，做出的重要贡献之一是在二战期间与布莱切利园（Bletchley Park）的同事们共同研制了名为“炸弹（Bombe）^○一”的密码破译机器，如图 1-1 所示，成功破解了从 1920 年起开始商用，德国人直到战败都认为绝不可能被破解的加解密方法“迷”（Enigma），使德军的军事部署在盟军面前再无秘密可言。图灵的成果直接加快了盟军获得战争胜利的速度^○二，因军事指挥通信被 Bombe 破译，引发了当时位列世界第一的德国俾斯麦号战列舰在丹麦海峡被英军伏击并围歼击沉。密码学的发展还导致了后来山本五十六的座机航线被盟军获知，进而遭拦截并击落等直接影响战争进程的事件^○一。在二战期间，图灵的工作成果虽然没有对公众公开，但在盟军的密码学圈子内部声名远扬，俨然是一颗耀眼的明星。

第 1 章 洪荒年代

5

○一 Bombe ：取这个名字是因为它是图灵及其团队基于原波兰密码破解机“Bomba”改进而来的，Bomba 可以破解简化情况（当时德军已经不再使用）下 Enigma 加密信息。另外，笔者特别说明一下，对 Enigma 的破译是一个团队而不仅仅是图灵一个人的工作成果，这段描述中使用图灵作为主语仅是行文需要。

○二 Jack Copeland（坎特伯雷大学教授，AlanTuring.net 的创建者）评估图灵的工作令盟军提 早两到三年获胜，相当于拯救了 1400 万到 2100 万人的生命。原文为“ If U-boat Enigma had not been broken, and the war had continued for another two to three years, a further 14 to 21 million people might have been killed. ”。

1942 年底，图灵被英国政府秘密派到美国，和美国海军交流破译德国的北大西洋潜艇舰队密码的研究成果。结束在华盛顿的交流后，图灵又来到了贝尔实验室，参与这里的安全语音通信设备的研发工作。这样，在贝尔实验室数学组任职的香农就获得了一个和图灵合作的机会。图灵当时是破译了包括希特勒通话在内的多个德军秘密通信的密码学破译专家，而香农当时的工作是通过数学方法证明“X系统”—这是美国总统罗斯福和英国首相丘吉尔之间的加密通信系统，是不可能被他人破译的，他们两位经过在密码学上“矛和盾”的攻防探讨，很快成为惺惺相惜的好友。

虽说图灵是去美国做交流的，但是军事上的事情，尤其是密码的加密和破解这种事情，只要不在军方明确允许的范围内，平常时间是不允许交流各自进展情况的，所以关于密码学上的话题，他们在工作之余是无法随意讨论的。所幸香农和图灵在计算机科学、信息科学上的兴趣和研究范围都极为广泛，经常吃饭时闲聊就聊到其他各种前沿领域。一次，他们在自助餐厅见面时，图灵给香农看了他还在剑桥大学读硕士学位时（1936 年）写的一篇论文^○一—《论可计算数及其在判定性^○二 问题上的应用》（“ On Computable Numbers, with anApplication to the Entscheidungs Problem ”），这篇论文是可计算领域的里程碑式作品。

6

第一部分 以智慧创造智慧

○一 官方资料称山本五十六的座机航线密电是被美国海军太平洋舰队破译中心破译的，并未提及图灵。图灵在 1942 年到美国交流与 1943 年 4 月山本五十六的座机被击落是否存在关联仅是民间的猜测。

可计算理论可以追溯到 1900 年，当时著名的大数学家大卫·希尔伯特（David Hilbert，1862—1943）在世纪之交的数学家大会上向国际数学界提出了著名的“23 个数学问题”。其中第 10 个问题是这样的：

“存不存在一种有限的、机械的步骤能够判断‘丢番图方程（Diophantine Equation）是否存在解？”

这里提出了有限的、机械的证明步骤的问题，用今天的话说就是“算法”。但在当时，通用计算机还要半个世纪之后才会出现，人们还不知道“算法”是什么。不过，当时数学领域已经有很多问题都与“算法”密切相关了，对“算法”，即“如何计算求解问题的步骤”的定义和是否可被算法计算的判定呼之欲出。

图灵这篇论文中提出的解决可计算性如何定义和度量的问题，其中的关键是引出了今天被称为“图灵机^○三”（Turing Machine）的概念模型。“图灵机”与“冯·诺依曼架构”并称现代通用计算机的“灵魂”与“躯体”，它对可计算性理论、计算机科学、人工智能都影响深远，可以说是一项改变了人类近代科学史的伟大发明。

第 1 章 洪荒年代

○一 提 到 硕 士 论 文， 香 农 自 己 的 硕 士 论 文“ A Symbolic Analysis of Relay and SwitchingCircuits”也是绝对的神作，这篇论文是布尔理论在电路中应用的开辟性著作，香农把一个世纪之前出现的布尔代数和电路中的继电器这两个风马牛不相及的事物结合在一起，提出在电路中，一个继电器向另一个继电器所传递的不是电，而是一种信息，自此开辟了逻辑电路和二进制计算的天地。他与图灵的这两篇论文，可谓整个 20 世纪最重要的硕士论文。

○二 可判定性”是指一个询问“真”或者“假”的问题是否可被回答。若不论一个问题答案为真或为假时均能得出该答案，则称这个问题或解决该问题时所用的算法是可判定的；若只能在答案为真时得出但在答案为假时不能做出判断，则称为半可判定的；若根本不能得出为真或为假的结论，则称为不可判定的。

○三 图灵的论文的地址为 http://onlinelibrary.wiley.com/doi/10.1112/plms/s2-42.1.230/abstract。

“图灵机”这种虚拟的计算机器实际上是一种理想的计算模型，它的基本思想是用机械操作来模拟人们用纸笔进行数学运算的过程。通俗地讲^○一，图灵把“计算”这件日常的行为抽象概括出来，看作下列两种简单动作的不断重复：

1）在纸带上写上或擦除某个符号。

2）把注意力从纸带的一个位置移动到另一个位置。

在每个动作完成后，人要决定下一步的动作是什么，这个决定依赖于人当前所关注的纸上某个位置的符号和人当前的思维状态。为了模拟人的这种运算过程，图灵构造出一台假想的机器，该机器由以下几个部分组成：

● 一条无限长的纸带 TAPE。纸带被划分为一个接一个的小格子，每个格子上包含一个来自有限字母表的符号，字母表中有一个特殊的符号“\_”表示空白。纸带上的格子从左到右依次被编号为 0，1，2，…，纸带的右端可以无限伸展。

● 一个读写头 HEAD。该读写头可以在纸带上左右移动，它能读出当前所指的格子上的符号，并能改变当前格子上的符号。

● 一套控制规则 TABLE。它根据当前机器所处的状态以及当前读写头所指的格子上的符号来确定读写头下一步的动作，并改变状态寄存器的值，令机器进入一个新的状态。

一个状态寄存器。它用来保存图灵机当前所处的状态。因为寄存器的数量是有限的，所以图灵机的所有可能状态的数目是有限的，并且规定有一个特殊的状态，称为停机状态，代表计算完成。

这种机器的每一部分都是有限的，但它有一个潜在的无限长的纸带，因此这种机器只是一个理想的设备，不会被真正地制造出来。图灵的论文证明了这台机器能模拟人类所能进行的任何计算过程。图灵机的图形表示如图 1-2 所示。

8

第一部分 以智慧创造智慧

○一 此处关于图灵机计算思想的通俗描述，来自维基百科（https://zh.wikipedia.org/wiki/ 图灵机）。

第 1 章 洪荒年代

9

图灵机思想的价值在于它虽然结构简单，但可以描述任何人类能够完成的逻辑推理和计算过程，换句话说，图灵机的计算能力是人类能够完成的所有计算的全集，只要一个问题是可判定的，且它的计算过程可以被符号和算法所表达出来，它就可以使用图灵机来完成计算。当时很多学者都无法想象这样一台听起来跟打字机差不多的东西，会是一个能够承载人类所有可以完成的逻辑和运算的计算模型。此前，“计算”能力是被视为与“思考”相类似的人类抽象能力，大家一时间很难接受“计算”可以被如此简单的模型所概括。

了解过“可计算性理论”（Computability Theory）这个学术分支历史的读者会知道，在图灵机被提出之前其实就已经有了能模拟人类所能进行的全部计算过程的模型。例如图灵硕博阶段的导师—普林斯顿大学的阿隆佐·邱奇（Alonzo Church，1903—1995）教授于 1928 年提出的“ Lambda 演算”就是其中之一。但相比其他计算模型，图灵机的优势在于它极为直观、易于理解，而且很容易通过机械或者电子技术来实现。因此，图灵机在其价值被人们发现后，迅速成为计算机解决“如何计算”问题的基础，在计算理论上也成为可计算性的对标物。当一个新的计算模型出现时，人们会判定它能否解决所有在算法上可计算的问题，如果能，它就被称为是图灵等价或者图灵完备的。今天，我们称某种程序设计语言是图灵完备的，意思也是所有可计算的算法都能够用这种语言来实现（如今天常见的 C、C++、Java、JavaScript 等都是图灵完备的，而 HTML、CSS 这些语言则不是图灵完备的^○一）。由于笔者是程序员，因此这里再多写一句题外话：由于图灵机的结构简单，不考虑编码效率和可读性的话，只需寥寥几个操作指令就能照着图灵机的定义实现一门图灵完备的语言，制造出脑洞大开的效果，大家有兴趣的话可以搜索一下“ BrainFuck”和“Whitespace”这两门语言看看。

10

第一部分 以智慧创造智慧

○一 笔者在 StackOverflow 上找到一篇通过 CSS3 的伪类定义来实现 Rule 110（一种元细胞自动机，被证明是图灵等价的）方法的文章，它的作者简直要把 HTML、CSS 给玩坏了。这里大家通过两门语言的差异对比有个直观感受就好，其他就不用纠结了。文章地址为https://stackoverflow.com/questions/2497146/is-css-turing-complete。

1.4 人工智能的萌芽

在与图灵的交流中，香农很快就理解并接受了图灵机的概念，并对此非常感兴趣。因为他与图灵都看到了一个令人激动的前景，既然图灵机这样一个并不复杂的计算模型就可以抽象人类的逻辑和计算能力，而逻辑和计算又是人类最具代表性的智能表现之一，那“思考”能力也就是“智能”是否也可以被一个模型承载抽象，并且被机器实现呢？图灵机是否可以扩展为概括所有智能活动的模型？如果图灵机不足以成为这种模型的话，是否有其他的抽象模型可以代替，成为人造智能的基石呢？

有必要再强调一下，当时是 1943 年，处于信息科学的萌芽期，连正经的通用电子计算机都还不曾出现的时代，并没有实际的图灵机和编程，图灵和香农（见图 1-3）所讨论的一切对智能的构想都停留在数学和哲学层面，而两位人工智能的先驱所讨论的这几个基础理论问题，在今天仍然是人工智能学界未能解决的问题，他们当时讨论的内容对计算机和人工智能的研究仍有很大的启发意义。

当时他们的讨论主要是围绕图灵机能否作为智能的基础模型、如何令机械拥有智能展开的，要解决这些问题，首先要解决的就是定义什么是“智能”。香农提出考虑机器智能问题时，应当把艺术、情感、音乐等方面的能力一并考虑进去，这很接近今天多元智能理论中对智能的理解。而图灵则不认可，他认为智能既然是由物质（指人类大脑）所承载的，就应该可以由物理公式去推导，可以用数学的方式去描述，而不应该把这些文化方面的内容包含进去。据AlanTuring: The Enigma 记载^○一，一次他们两个在讨论智能的定义时发生了争论，图灵反驳香农时是这么说的：“不！我对如何建造一颗无所不能的大脑完全不感兴趣，我只要一颗并不太聪明的大脑，和美国电报电话公司董事长的脑袋那样就差不多行了！”如果这位“躺枪”的董事长先生（贝尔实验室是 AT&T 下辖的研究机构，董事长即他们两个的老板）在场的话，大概不会同意图灵给智能所下的定义。

第 1 章 洪荒年代

11

对于机器如何实现智能这个问题，图灵提出了两条可能的发展路线^○二。一条是基于建设“基础能力”的方法，通过编写越来越庞大、完善的程序，使机器具备越来越多的能力，譬如可以与人下棋、可以分析股票、可以识别图形等这样的能力，图灵认为这是完全可以做到的。但他更有兴趣的是另一条，即基于“思维状态”来建造大脑。这条路线的指导信条是，人类大脑一定存在着某种内在机制来产生智能，因为并没有什么更高级的神秘力量在为人脑编程，所以一定存在某种方法，可以使机器自动地学习，就像人类大脑一样。图灵进一步解释道：新生儿的大脑是不具备智能的，因此，找到人类大脑获得智能的途径，然后应用于机器上，使机器可以自己学习成长，成为机器掌握任何领域技能的一揽子解决方案。

在美国交流期间，图灵和香农未能解决“如何定义智能”“图灵机能否作为智能的承载模型”等问题，但是他们在贝尔实验室的一系列关于智能的讨论，代表这个时期学者对“机器和智能”思考的萌芽，是人工智能从“科幻”走向“科学”的第一步。图灵回到英国之后，与香农仍然保持着联系，香农还到英国回访过图灵，他们仍然为解决这几个问题而不懈努力。在本章中，笔者将继续以图灵的工作为主线进行讲解，而香农的研究工作也间接地导致了人工智能史上另一个重要里程碑事件的发生，这就是下一章的内容了。

12

第一部分 以智慧创造智慧

○一 该 记 载 来 自 Andrew Hodges 编 写 的 Alan Turing: The Enigma， 该 书 于 1992 年 出 版，2012 年引入中国，中文书名叫《艾伦·图灵传：如谜的解谜者》，该书还被改编成一部电影，名为《模仿游戏》。

○二 这段记载同样来自Alan Turing: The Enigma，没有历史资料记载图灵直接说过这样的话，这是 Alan Turing: The Enigma 的作者根据图灵的工作和论文的观点总结的。

1.5 图灵测试：何谓智能

在 1945 年到 1947 年期间，图灵从美国回到英国之后居住在伦敦的汉普顿区。这段时间他为英国国家物理实验室（National Physical Laboratory，NPL）工作，工作的具体内容是设计一款名为“自动计算引擎”（Automatic ComputingEngine，ACE）的通用电子计算机，如图 1-4 所示。1946 年 2 月，图灵发表了世界上详细论述带程序存储功能（Stored-Program）的计算机体系结构的最早论文之一^○一。但是由于政府决策者的短视，ACE 完成理论设计后，反而陷入了一连串研发电子计算机的工作是否值得现在就去投入的争论之中，并未能立刻进入建造阶段。图灵因此感到心灰意冷，离开 NPL 回到大学校园（剑桥大学和曼切斯顿大学），专心研究机械与智能去了。

关于 ACE 的历史，其实很值得详细书写一番，如果 ACE 当时立即启动建造，将很有可能和冯·诺依曼（Von Neumann，1903—1957）的“离散变量自动电子计算机”（Electronic Discrete Variable Automatic Computer，EDVAC）^○一竞争“现代计算机的鼻祖”的头衔（ACE 建造工作重新启动之后，在 1950 年竣工，EDVAC 则在 1949 年完成，两者完成时间仅相差不到1 年），也许今天学校的计算机课本讲到体系结构时就不再是冯·诺依曼架构了^○二。图灵和冯·诺依曼都是数学和计算机科学领域的天才，图灵在普林斯顿大学跟随阿隆佐·邱奇攻读博士学位时，与冯·诺依曼的办公室相邻，双方在计算机方面有过深入交流。后来虽然两人分处英、美两国独立研究，但对计算机体系结构的观点依然高度一致^○三，只是运气上冯·诺依曼要比图灵好得多。图灵关于 ACE 的工作和人工智能关系有限，我们就不再花费笔墨在这上面了。

第 1 章 洪荒年代

13

○一 世界上最早的关于带程序存储架构的论文是冯·诺依曼发表的关于 EDVAC 的著名论文“ First Draft of a Report on the EDVAC”，其实也就比图灵的论文早半年，但是详细程度不如图灵的论文。

○二 图片来源：https://www.express.co.uk/news/uk/450892/Gay-rights-campaigner-calls-for-investigation-into-Alan-Turing-s-death。

由于英国政府的保密要求，回到剑桥后，图灵所做的关于机械智能的研究在当时并未公开发表（图灵的论文《智能机器》（“ Intelligent Machinery”）写于 1948 年，直至 1992 年才在《阿兰·图灵选集》中发表）。直到 1950 年，图灵在《心灵》（Mind）杂志上发表了另一篇划时代的论文：《计算机器和智能》（“Computing Machinery and Intelligence”）^○四，如图 1-5 所示。笔者相信大部分读者都没有听说过这篇论文，但肯定有很多人听说过“图灵测试”（Turing Test）^○五，正是这篇论文提出了著名的“图灵测试”。可以说，正是因为这篇论文对图灵研究工作的总结，使得后来图灵被世人冠以人工智能之父的荣耀。

14

第一部分 以智慧创造智慧

○一 EDVAC：离散变量自动电子计算机，是第一台冯·诺依曼架构的计算机。

○二 对于第一台计算机，很多人可能有所误解，1946 年建成的 ENIAC 是第一台“通用电子计算机”，但是它并不是冯·诺依曼架构的（无法存储程序，必须通过连接线缆来重新编程），我们现在广泛使用的计算机，从“血缘”关系上讲更贴近于 EDVAC 的后代。

○三 EDVAC 报告中最核心的概念是“存储程序”（Stored-Program），冯 · 诺依曼把这个概念的原创权公正无私地给予了图灵。正像图灵专家、新西兰哲学家杰克 · 寇普兰（JackCopeland）考证的，冯 · 诺依曼生前向他的同事多次强调：计算机中那些没有被巴贝奇预见到的概念都应该归功于图灵。所谓存储程序就是通用图灵机。

○四 《计算机器和智能》论文地址为 www.loebner.net/Prizef/TuringArticle.html。

○五 https://zh.wikipedia.org/wiki/ 图灵测试。