1.3 图灵机，计算的基石

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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