第7章 信息论

——我想要的不过只是一颗寻常的大脑建立一套有关信息及其处理的理论，有点儿像建造一条横贯大陆的铁路。你可以从东海岸出发，先试着理解信息是如何处理的，然后向西迈进。或者你也可以从西海岸出发，先试着理解信息到底是什么，然后向东深入。我们希望的是，两条铁轨能在中间会合。

——乔恩·巴怀斯（1986）

1943年初，正值第二次世界大战如火如荼之时，两位志趣相投的思想家，克劳德·香农和阿兰·图灵，经常会在贝尔实验室的食堂共进午餐，但他们对彼此的工作都守口如瓶，因为那事关机密。 两人都在从事密码分析工作，甚至连图灵来到贝尔实验室这件事都涉及机密。他是搭乘“伊丽莎白女王号”，辗转躲过德军的U型潜艇方才来到美国。而之所以能够躲过劫难，还要归功于他之前在布莱切利庄园成功破解了德军用来进行机要通信的密码——恩尼格玛（Enigma），该密码也用在了潜艇的通信上。当时香农正致力于X系统（SIGSALY）的工作，该系统是用来加密在五角大楼的罗斯福与在战争办公室的丘吉尔之间的语音通话。它先对模拟语音信号每秒采样五十次（即“量化”或“数字化”），然后对采样信号应用一个随机密匙，这个密匙与工程师们很熟悉的电路噪声十分相似。香农并不设计这套系统，他的任务是从理论上分析该系统，并希望证明它不可破解。他成功地做到了这一点。后世的人们清楚地认识到，正是大西洋两岸这些人的通力合作才使密码学从一门艺术变成了一门科学。但在当时，密码制作者和密码破解者却无法对此开怀畅谈。

既然密码这个话题不能拿到台面上讨论，图灵就给香农看了一篇他在七年前写的论文《论可计算数》，其中讨论了一种理想计算机器的力量和局限。他们谈论的另一个话题则是双方都感兴趣的，即机器是否可能学会思考。香农提议可以把“文化的东西”，比如音乐，也灌输进电子大脑中。双方的讨论有时会变得十分激烈，图灵曾有一次在大庭广众之下高声反驳说：“不，我对建造一颗强大的大脑不感兴趣，我想要的不过只是一颗寻常的大脑，跟美国电报电话公司董事长的脑袋瓜差不多即可。” 在1943年讨论什么思考机器似乎有点大言不惭，毕竟晶体管和电子计算机都还没有出现。不过，香农和图灵所交流的愿景与电子学无关，而只与逻辑学有关。

机器能思考吗？这个问题出现的历史相对较短，且看上去有点奇怪——说奇怪，是因为机器结结实实就是一堆物质啊。查尔斯·巴贝奇和爱达·洛夫莱斯差不多是最早研究这个问题的人，但他们早已被人遗忘。而现在，阿兰·图灵迈出了前所未闻的一步：他首先设想了一种机器，它在思维领域具备无与伦比的力量；然后他证明了，这样的机器不能做什么。他的机器在当时并未变成现实（不过现如今，它已是无处不在），这只是一个思想实验。

与机器能做什么的问题密切相关的是另一个问题，即什么样的任务是机械的（这个旧词被赋予了新的重要性）。既然机器可以演奏音乐、捕捉图像、瞄准高射炮、连接电话通话、控制组装线，还可以进行数学计算，“机械的”一词已然显得不那么贬义。不过在当时，也只有那些胆小而迷信的人才会想象机器有朝一日会变得有创造力、独到、自主，毕竟这些特性与“机械的”一词的通常意涵（自动的、被动的、循规蹈矩的）大相径庭。哲学家们发现这个词很有用。在他们看来，一个既涉及智能又可被称为机械的例子是算法：这个新术语表示的是某种古已有之的东西（体现在如菜谱、指令集、分步步骤等当中），只是现在它要求人们的正式承认。巴贝奇和洛夫莱斯与算法打了那么久交道，却没有给它加以命名。而算法在20世纪被赋予了一个核心位置，也正是从此开始的。

1936年，当图灵将他关于可计算数的论文呈交给他的教授时，他是剑桥大学国王学院的研究员，两年前刚从那里本科毕业。这篇论文的完整标题以一个华丽的德语单词收尾：《论可计算数及其在判定性问题上的应用》（“On Computable Numbers, with an Applicationto the Entscheidungsproblem” ） 。 所 谓 “ 判 定 性 问题”（Entscheidungsproblem）是大卫·希尔伯特在1928年国际数学家大会上提出来的。身为可能是他那个时代最具影响力的数学家，与罗素、怀特海一样，希尔伯特也满怀热情地致力于为全部数学奠定一个坚实的逻辑基础。他曾宣称：“在数学里，没有‘我们将来也不知道' 。”当然，数学里有很多未解之题，其中一些还很著名，如费马大定理和哥德巴赫猜想——这些命题看上去是成立的，但尚未得到证明。 大多数人认为，这些命题只是暂时尚未得到证明。他们假设，或者说相信，任何数学真理都能被证实，只是时间早晚而已。

判定性问题问的就是，能否找到一个严格的、分步的算法，通过它，给定一种演绎推理的形式语言，人们就可以自动化地进行证明。

这呼应了莱布尼茨的梦想，即通过一系列机械的规则来表示所有有效的推理过程。虽然希尔伯特是以问题的形