第2章　计算机祖孙三代

2.1　计算机爷爷——图灵机模型

2.1.1　艾伦·图灵是个科学家

艾伦·图灵（Alan Turing，1912—1954）如图2-1所示。这个名字无论是在计算机领域、数学领域、人工智能领域还是哲学、逻辑学等领域，都可谓掷地有声。艾伦·图灵是计算机逻辑的奠基者，许多人工智能的重要方法也源自这位伟大的科学家。

100多年前，艾伦·图灵诞生在一个文化和科技水平都与现在完全不同的时代里，他为计算机领域奠定了不可埋没的基础，没有他就没有计算机的今天。

他在24岁时提出了图灵机理论，31岁时参与了Colossus（第二次世界大战时，英国破解德国通信密码的计算机）的研制，33岁时构思了仿真系统，35岁时提出自动程序设计概念，38岁时设计了“图灵测试”；在后来还创造了一门新学科——非线性力学。他的业余爱好是长跑，如图2-2所示。

虽然艾伦·图灵去世时只有42岁，但在其短暂而离奇的生涯中的那些科技成就，已让后人享用不尽。人们仰望着这位伟大的英国科学家，把他称为“计算机之父”“人工智能之父”“破译之父”，有人甚至认为，他在技术上的贡献及对未来世界的影响几乎可与牛顿、爱因斯坦等巨人比肩。

1936年，还在剑桥国王学院就读的艾伦·图灵发表重要论文《论可计算数及其在判定问题上的应用》（On Computable Numbers，with an Application to the Entscheidungsproblem），提出“算法（algorithm）”和“计算机（computing machine）”两个核心概念，一直让人们受用到今天。

当时的图灵机还只能计算有限的实数，但它的符号记录方法为以后的计算机发展奠定了基础理论，基于此，人类首次产生了符号处理的概念，并开始把研究重点转向可改变的编码程序，这就是今天软件的前身。

1939年第二次世界大战爆发，正在为英国国家密码机构工作的艾伦·图灵和其他科学家一起着手研究如何破解敌人的密码，他果然不负众望，成功破译了德国军方使用的著名通信密码系统Enigma（谜）。于是第一台电子图灵机被设计制造出来，做出重大贡献的艾伦·图灵获得了政府颁发的OBE奖。

1946年，艾伦·图灵发表论文阐述存储程序计算机的设计。他的成就与研究离散变量自动电子计算机（Electronic Discrete Variable Automatic Computer）的约翰·冯·诺依曼（John von Neumann）同期。艾伦·图灵的自动计算机与约翰·冯·诺依曼的离散变量自动电子计算机都采用二进制，都以“内存储存程序以运行计算机”打破了那个时代的旧有概念。

1950年，艾伦·图灵的一篇里程碑式的论文《机器能思考吗？》又为人类带来了一个新学科——人工智能。为了证明机器是否能够思考，他又发明了“图灵测试”（Turing Test），图灵测试在今天仍被沿用。他指出，最好的人工智能研究应该着眼于为机器编制程序，而不是制造机器。而他在论文中预测的计算机发展过程中将会出现的一些问题，至今仍未被解决。

2.1.2　图灵机模型

学习计算机科学的读者都应该知道，在计算机基础理论中有着名的“图灵机”和“图灵测试”。这些理论简洁地概括了图灵伟大贡献的一部分：他是第一个提出利用某种机器实现逻辑代码的执行，以模拟人类的各种计算和逻辑思维过程的科学家。而这一点，成为后人设计实用计算机的思路来源，成为当今各种计算机设备的理论基石。当今计算机科学中再常用不过的程序语言、代码存储和编译等基本概念，就是来自艾伦·图灵的原始构思。

图灵机（Turing Machine）又称为图灵计算机，是艾伦·图灵提出的一种抽象计算模型，即将人们使用纸和笔进行数学运算的过程进行抽象，由一个虚拟的机器替代人们进行数学运算。

图灵机是一个抽象的机器，它有一条无限长的纸带，纸带分成一个一个的小方格，每个方格有不同的颜色；有一个机器头在纸带上移来移去。机器头有一组内部状态，还有一些固定的程序。在每个时刻，机器头都要从当前纸带上读入一个方格信息，然后结合自己的内部状态查找程序表，根据程序输出信息到纸带方格上，并转换自己的内部状态，然后进行移动。

2.1.3　计算机界的诺贝尔奖

图灵奖（Turing Award）是美国计算机协会（ACM）于1966年设立的，专门奖励那些对计算机事业做出重要贡献的个人。其名称取自世界计算机科学的先驱、英国科学家、英国曼彻斯特大学艾伦·图灵，这个奖设立目的之一是纪念这位现代计算机奠基者。获奖者必须是在计算机领域具有持久且重大的先进性的技术贡献。大多数获奖者是计算机科学家。

图灵奖是计算机界最负盛名的奖项，有“计算机界的诺贝尔奖”之称。图灵奖对获奖者的要求极高，评奖程序也极严，一般每年只奖励一名计算机科学家，只有极少数年度有两名以上在同一方向上做出贡献的科学家同时获奖。