2.3 图灵机与冯·诺依曼计算机

2.3.1 图灵与图灵机

1. 图灵

阿兰·麦席森·图灵（Alan Mathison Turing），如图2-17所示，英国著名数学家、逻辑学家、密码学家，被称为计算机科学之父、人工智能之父。1938年在美国普林斯顿大学取得博士学位，第二次世界大战爆发后回到剑桥，后曾协助军方破解德国的著名密码系统Enigma，帮助盟军取得了第二次世界大战的胜利。图灵于1954年6月7日在曼彻斯特去世，他是计算机逻辑的奠基者，提出了“图灵机”“图灵测试”等重要概念。人们为纪念他在计算机领域的卓越贡献而专门设立了“图灵奖”。

2. 图灵机的基本思想

图灵认为自动计算就是人或者机器对一条两端无限延长的纸带上的一串0和1，执行指令，一步步地改变纸带上的0和1，经过有限步骤得到结果的过程。机器按照指令的控制选择执行操作，指令由0和1表示，例如，00表示停止，01表示转0为1，10表示翻转1为0，11表示移位；计算的任务可以通过将指令编写程序来完成，如00，01，11，010，10，00…。数据被制成一串0和1的纸带送入机器，机器读取程序，按照程序的指令顺序读取指令，读取一条指令执行一条指令，如图2-18所示。

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

图灵机模型被认为是计算机的基本理论模型，它是一种离散的、有穷的、构造性的问题求解思路，一个问题的求解可以通过构造器图灵机来解决。

著名的图灵可计算问题：凡是能用算法解决的问题，也一定能用图灵机解决；凡是图灵机解决不了的问题，任何算法也解决不了。

3. 图灵测试

图灵测试，又称“图灵判断”，是图灵提出的一个关于机器人的著名判断原则，它是一种测试机器是否具备人类智能的方法。如果计算机能在5min内回答由人类测试者提出的一系列问题，且其超过30％的回答让测试者误认为是人类所答，则计算机通过测试。

如图2-20（a）所示，图灵测试的方法是在测试人与被测试者（一个人和一台机器）隔开的情况下，通过一些装置（如键盘）向被测试者随意提问。问过一些问题后，如果测试人不能确认被测试者30％的答复哪个是人、哪个是机器的回答，那么这台机器就通过了测试，并被认为具有人类智能。

2014年6月7日在英国皇家学会举行的“2014图灵测试”大会上，聊天程序“尤金·古斯特曼”（Eugene Goostman）首次通过了图灵测试，如图2-20（b）所示。这一天恰好是计算机科学之父阿兰·麦席森·图灵逝世60周年纪念日。在活动中，“尤金·古斯特曼”成功伪装成一名13岁男孩，回答了测试者输入的所有问题，其中33％的回答让测试者认为与他们对话的是人而非机器，这是人工智能乃至于计算机史上的一个里程碑事件。

2.3.2 冯·诺依曼计算机

1946年，美籍匈牙利科学家冯·诺依曼领导的研究小组发表了关于EDVAC（Electronic Discrete Variable Automatic Computer，电子离散变量自动计算机）的论文，具体地介绍了制造电子计算机和程序设计的新思想，宣告了电子计算机时代的到来。

EDVAC是第一台具有现代意义的并行计算机，与ENIAC不同，EDVAC首次使用二进制而不是十进制。整台计算机使用了大约6 000个电子管和12 000个二极管，功率为56kW，占地面积45.5m2，重量为7 850kg，使用时需要30个技术人员同时操作，如图2-21所示。

冯·诺依曼在EDVAC的研究中，提出了计算机的逻辑体系结构和存储程序的理论，即冯·诺依曼计算机，主要包括以下内容。

（1）计算机由运算器、控制器、存储器、输入设备和输出设备5个部件构成。它以运算器和控制器为中心，这两部件构成了如今熟知的中央处理单元（Central Processing Unit，CPU），如图2-22所示。

（2）确定了计算机采用二进制，指令和数据均以二进制数形式存储在存储器中。

（3）计算机按照程序规定的顺序将指令从存储器中取出，并逐条执行。

计算机系统的5个部件的主要功能如下所述。

1. 运算器

运算器（Arithmetic Logic Unit，ALU）也称算术逻辑运算单元，它主要完成数据的加、减、乘、除等算术运算和与、或、非等逻辑运算。

2. 控制器

控制器（Control Unit）也称控制单元，负责读取指令、分析指令和执行指令，调度运算器完成计算。

3. 存储器

存储器负责存储数据和指令。存储器是存储信息的部件，其结构如图2-23所示，按照地址划分为若干存储单元，每个存储单元由若干存储位组成，一个存储位可以存储一个0或1。每个存储单元由一条地址线Wi控制其读写，当Wi有效时读写对应的存储单元。每个存储单元有一个对应的地址编码，由An-1…A1A0进行编码，通过译码器将每个地址编码An-1…A1A0译出其对应的地址线Wi控制对应存储单元的读写。因此，n位地址线可以控制读写2n个存储单元，即存储容量为2nB。

输出缓冲器，控制从存储器中读取或者写入数据，存储单元的数据通过Dm-1…D1D0数据线读写。

4. 输入设备

输入设备负责将数据和指令从外部输入计算机中。

5. 输出设备

输出设备将计算机中的二进制信息以用户能接受的形式呈现。

2.3.3 存储程序控制原理

1. 指令、指令系统和程序

为了能够让计算机完成任务，需要为计算机提供一系列命令。

（1）指令：也称机器指令，是指计算机完成某个基本操作的命令，是计算机可以识别的二进制编码。指令能被计算机硬件理解并执行，是程序设计的最小语言单位。

一条计算机指令使用一串二进制代码表示，代码的位数称为指令长度。它通常包括操作码和操作数两部分。操作码确定指令的功能，如进行加、减、乘、除等运算。操作数也称地址码，指明参与运算的操作数本身或操作数存储的地址。其格式如下：

计算机的字长是指计算机能一次直接处理的二进制数据的位数。指令长度可以和机器字长相同，也可以不相同。

（2）指令系统：一台计算机所有机器指令的集合称为计算机的指令系统。不同种类计算机的指令系统的指令数目与格式也不同。指令系统越丰富完备，编制程序就越方便灵活。

（3）程序：由指令组成，是为解决某一特定问题而设计的有序指令的集合，是为了得到某种结果而由计算机等具有信息处理能力的装置执行的指令序列。

2. 指令执行过程

计算机按照程序的执行顺序逐条取出存储器中的指令，传输到CPU后执行。指令的执行过程如下所述。

（1）取指令阶段。在控制器的控制下，将存储器中的指令读入CPU的指令寄存器中。

（2）分析指令阶段。也称译码阶段，是指由指令译码器将指令代码转换为电子器件操作。如果指令中包含操作数，还要从寄存器中读取操作数。

（3）执行指令阶段。在控制器的控制下，执行指令的具体操作。

（4）写回结果阶段。将最终结果写入相关寄存器或存储器。