第7章 信息论

于这位停机检察官自己在看着自己［在看着自己（……）预测自己的行为时预测自己的行为］预测自己的行为时预测自己的行为”。 物理学同样新近遇到了类似的难题：海森堡的不确定性原理。图灵在听说这个原理后，采用自指的说法对此进行了表述：“过去我们一直假定，在科学中，只要知道宇宙在某一时刻的全部状态，我们就能把宇宙所有的未来状态都预测出来……但更为现代的科学却认为，当我们面对原子和电子时，我们无法知道它们的全部确切状态，因为我们所用的仪器本身就是由原子和电子构成的。”

从巴贝奇的差分机到图灵的通用机，一个是笨重的庞然大物，一个是优雅的抽象虚构，两者相隔了一个世纪。图灵从没打算成为一个循规蹈矩的机器操作员，就像多年以后数学家和逻辑学家赫伯特·恩德滕所描述的那种“勤勉努力的办事员，遵照着给他的指令，在供应充足的纸张上做着运算”。 相反，一如爱达·洛夫莱斯，图灵是个程序员。他将自己想象成一台计算机，关注自己思维过程中一步步的逻辑，并将这些心智过程加以提炼萃取，得出其最小的组分，也就是信息处理的原子。

——图灵和香农都在使用编码，只是图灵是把指令编码成数，将十进制数编码成0和1，而香农是对基因、染色体、继电器和开关编码。他们的灵思巧智都应用在了如何将一类事物映射到另一类事物（例如，代数函数与机器指令，逻辑运算符与电路），也就是找出两类事物之间严格的对应关系上。在他们心智的武器库中，符号运算以及映射的思想占据着举足轻重的地位。当然，这种编码转换不是为了遮蔽事实，相反是为了揭示事实：比如说，借此可以发现苹果和橘子归根结底是等价的，或即便不等价，也是可相互替代的。但很快，两人便都被战争引入了当时如日中天的密码学领域。

图灵的母亲常问他，他的数学有什么用。对此早在1936年，他就曾在给母亲的信中透露，自己已经找到了当时正在研究的可计算数的一种可能应用：“它回答了‘最一般的编码或密码是什么样的'问题，并且（自然而然）使得我可以构造许多特殊的、有趣的密码。”

他又补充道：“我猜我能以大价钱把这些密码卖给政府，但我相当怀疑这样做是否道德。”图灵机的确能够制作密码，不过英国政府当时面对的却是另外一个难题。随着战争阴影的逼近，解读拦截到的德军电报和无线电情报的任务，便落到了对外称为“政府编码与密码学校”（GC&CS）的密码破解机构肩上。该机构原本隶属于海军部，后来转移到了外交部，最早的成员包括语言学家、办事员和打字员，但没有数学家。1938年夏，图灵应召进入该学校，并在次年随学校从伦敦撤到了伯明翰郡的布莱切利庄园。这时他的同事中还有了几位国际象棋和填字游戏冠军。很显然，古典语言学对于现在的密码分析工作已经力不从心了。

一台缴获的恩尼格玛密码机

德国的密码系统名为恩尼格玛，是一种多码加密装置。密码机有手提箱大小，里面有多个转子，外面则有键盘和信号灯。这个密码系统源自著名的维吉尼亚密码，它曾号称是不可破译的密码，直到1854年被查尔斯·巴贝奇所破解。巴贝奇所用的数学方式为政府编码与密码学校的早期工作提供了帮助。同样提供了帮助的是波兰密码学家，他们在战前曾成功破解过德军早期的恩尼格玛密码系统。在“八号营房”，图灵从理论入手，最终不仅从数学上，还从物理上解决了这个难题。

这意味着要建造一台机器，用来逆推恩尼格玛加密过的数据。图灵的首台机器只是个使用假想纸带的虚幻之物，但这台绰号“炸弹”（Bombe）的机器却是个体积将近三立方米的庞然大物，里面藏着重达一顿的电线以及油腻腻的金属零件，它们有效地将恩尼格玛密码机的转子映射成了电路。这项在布莱切利庄园取得的科学成就，在战争期间及之后的三十年里一直都是机密，但它对战争结局的影响甚至要超过曼哈顿计划制造出的真正炸弹。到了战争后期，图灵的“炸弹”每天要破解数以千计的敌军情报，这样的信息处理规模是史无前例的。

尽管在贝尔实验室一起用餐时，图灵和香农都丝毫没有提及这方面的内容，但他们的确间接地谈到了图灵对于如何度量这些东西的一个构想。布莱切利庄园的分析师会对汇聚到此的各种讯息（有些难以确定，有些又互相矛盾）进行权衡，以便评估它们当中包含一定事实的概率，比如恩尼格玛的某种编码设置或潜艇的可能位置等。图灵感到这其中有些东西需要在数学上加以度量。不过，他关注的不是传统意义上的概率，用比值比（如3比2）或一个0到1的数（如0.6，或60%）来表示。他更在意的是引致概率变化的数据：影响概率的因子，有点类似于皮尔士的证据权重。他发现使用对数标度比较方便，这样乘法运算就会变成加法运算。他还为此发明了一个新单位，叫做“班”（ban） 。班是以10为底，因此，1班意味着使某一事实成立的可能性增大十倍所需的证据权重。对于粒度更小的度量需求，还可以使用分班和厘班。

与此同时，香农也在沿着类似的轨迹进行着摸索。

在纽约西村的贝尔实验室旧总部，香农发展出了一套密码学