Page 35 - 信息的脉络

·第一部分·
第二节 伟大的图灵机

有时候，正是那些意想不到的人，成就了无人能成之事。
——阿兰·图灵

1900 年，希尔伯特在世纪之交的数学家大会上向国际数学界提出了 23 个重要
且尚未解决的数学问题，其中第二个问题是“算术公理系统的无矛盾性”。1928 年，
在博洛尼亚国际数学会议上，希尔伯特把这个问题描述得更加精确。对希尔伯特

提出的三个问题，传记作家安德鲁·霍奇斯描述为：“第一个，数学是否具有完
全性。换言之，每个命题要么被证明，要么被否决；第二个，数学是否具有相容性；
第三个，数学是否具有可判定性。”
最后这个问题就是著名的可判定性问题。哥德尔对前两个问题作出了否定的
回答，但对可判定性问题，阿兰·图灵准备出场。

1935 年，23 岁的图灵听了麦克斯·纽曼一场关于“数学基础”的演讲，在快
要结束的时候，纽曼提到了哥德尔定理，并明确指出希尔伯特的第三个问题（可
判定问题）尚未得到解答，纽曼提的问题促使图灵开始思考图灵机：是否存在一

种确定的方法或“机械过程”，将之应用于一个数学命题，即可得到这个命题是
否可证的结论。
纽曼的“机械过程”的说法给了图灵很大共鸣，他决定独立研究希尔伯特问题。
图灵将“可计算性”这个概念解释为一台简单机器执行计算的能力。他设想

有一台机器可以像人类计算者一样进行工作，并且必须遵守一套规则。图灵把这
种机器理想化，它不使用标准纸张，使用的是长长的纸带，上面有她要做的计算。
纸带分成了一个个的小方格，每次机器可以从一个效仿者读取或写入一个符号。
对真实的人类计算者来说，只使用一条带有单个符号行的纸带做计算是个非常枯

燥的事情，但是机器完全可以采用这种方式进行计算。图灵设想这个“人类计算器”
有许多不同的状态，这些状态会告诉机器应该如何使用从纸带方格中读取的信息。
因此，她会从特定状态开始，检查纸带中每个方格中的内容。在读取了方格中的
符号之后，它可以覆写方格中的符号，转换成一种新状态，移动到下一个方格以

处理下一个符号。它的装填决定如何处理读取到的符号，如是否应该将其作为加
法或乘法的一部分。图灵设想，人类计算者只需要有限的集中状态就能完成制定
的计算。通过把人类执行计算的过程分成简单的步骤，图灵提出了一个非常简单
的机器，用来模拟人类计算者的所有行为，通过算法步骤完成相同的计算。

图灵机有一条无限长得纸带，纸带分成了一个个的小方格，每个小方格里至
少包含一个符号。在算法的每一个步骤中，这种机器头可以往左或往右移动到下

• 19 •