第7章 信息论

式提出，但他是个乐观主义者。他认为或者说希望，自己已经知道答案了。也正是在这数学和逻辑学命运的关键时刻，哥德尔提出了他的不完全性定理。至少表面上看，哥德尔的研究彻底打破了希尔伯特的乐观主义，就像之前对罗素所做的。但实际上，哥德尔并没有回答判定性问题。希尔伯特曾区分了三个问题：

数学是完全的吗？

数学是一致的吗？

数学是可判定的吗？

哥德尔证明了，数学不可能既是完全的，又是一致的，但他并没有明确地回答第三个问题，至少没有针对全部数学给出明确答案。这样，即便某个特定的、封闭的形式逻辑体系必然包含一些从体系内部既不能证实也不能证伪的命题，但它还是可能由一个可以说是外部的裁判（如该体系外的逻辑或规则）加以判定。

阿兰·图灵，当时只有二十二岁，他对于大部分的相关文献都不熟悉，工作也喜欢独来独往，有时他的教授甚至都担心他会变得“习惯于孤独”。 在论文中，他提出了一个（表面上看）完全不同的问题：所有的数都是可计算的吗？这是个出人意料的问题，毕竟几乎没有什么人考虑过不可计算的数。大多数人所使用或考虑的数，根据定义都是可计算的。有理数是可计算的，因为它们可以表示成两个整数的商：a/b。代数数是可计算的，因为它们是多项式方程的解。一些超越数，如著名的π和e，也是可计算的，人们事实上一直都在计算它们。对此，图灵提出了一个看似温和的命题：有些数可命名、可定义，却是不可计算的。

那这句话是什么意思？图灵将可计算数定义为，其小数表达式可在有限步骤内计算出来。他说：“这样定义的合理性，在于人类记忆是有限的这一事实。” 图灵同时把计算定义为一个机械的过程，一种算法。人类在解决问题时常常会借助直觉、想象或灵光一闪——这些乍看上去可以说是非机械的计算，但深究起来或许又只是步骤被隐藏起来的机械计算罢了。图灵需要把这些只可意会不可言传的东西去除。因此，他问了一个直截了当的问题：要是机器，它会怎样做？“根据我的定义，如果一个数的小数表达式可以被机器写出来，那么它就是可计算的。”

但在当时，没有一台真实的机器可供参考。从事计算工作的依然是“计算员”，几乎所有的计算工作仍旧是在纸面上运算完成的。不过，图灵确实想到了一台信息处理机器可以作为起点，那就是打字机。早在他十一岁还在上寄宿学校时，他就曾想过要发明一台打字机。他在给父母的信中写道：“你看，这些有趣的圆圈一面刻出字母的形状，从圆圈Ⓐ开始，排列在一个印台四周，这样压下去就可以印出一个字母，不过图上没有把字母全部画出来。” 当然，打字机不是自动的，与其说它是台机器，还不如说它是个工具。它不会往页面上倾吐一连串文字，相反，是纸在一格格移动位置，然后字锤在上面敲出一个个字符。基于这样的模型，图灵想象出了另一种至纯至简的机器。也正因为这样一部机器只存在于想象当中，所以无需考虑图纸设计、技术规格或专利申请等环节的细节问题。与巴贝奇一样，图灵的机器也是用来计算数，只是他不必担心各种技术限制，因为他根本就没有打算去建造这部机器。

图灵列出了他的机器必备的很少几个组件：纸带、符号和状态。

这些组件需要一一加以定义。

纸带之于图灵机，就如同纸张之于打字机。不过，打字机利用了纸张的两个维度，而图灵机只利用了它的一个维度——纸带是一长条纸，并被分成了一个个的方格。图灵写道：“在初等算术中，人们有时会用到纸张的二维特性，但这种做法是可以回避的。并且我认为，人们将会认识到，纸张的二维特性对计算来说并不是必不可少的。”

图灵机的纸带被想象成无限长的，也就是说，它取之不尽，用之不竭。但在任意给定时刻，在“机器内”的只有一个方格。纸带（或机器）可以左右移动至前后方格。

符号可以写在纸带上，每个方格写一个。那么可以使用多少个符号呢？这个问题需要费些思量，尤其是如果限定只能使用有限个符号（如果允许无限个符号，那么符号之间的差异将会任意小）。但这个限定并不会有太大影响，因为“总是可以用符号序列来代替单个符号”。图灵发现，至少在欧洲语言里，一个由众多字母拼成的单词是被视为单个符号（相反，汉字则“试图使用可枚举的无限个符号”）。如果17和999,999,999,999被视为单个符号的话，那么阿拉伯数字将有无限个，但图灵更愿意把它们视为复合符号。事实上，为了符合机器的极简主义精神，他选择了最简单的两个符号：二进制记号，0和1。符号不仅可以写入纸带，还可以读出——图灵当时使用的是“扫描”一词。在现实中，当时显然还没有出现可以把纸面上的符号扫描进机器中的技术，但等效的东西却早已有之，如用在制表机上的打孔卡片。图灵还设定了另一个限制：机器每次只能“感知”（使用这样拟人化的用语也是别无选择）一个符号，也就是在机器内的方格上的那个符号。

状 态 则 要 费 更 多 笔 墨 解 释 。 图 灵 使 用 了 “ 格局”（configuration）一词，并指出，不同的格局对应的