2.5 101页报告改变了世界

2.5.1 又笨又快的图灵机

从上面读者知道了存储和加法是如何实现的，但是这还不是程序，那么一个程序是如何在计算机内部执行的呢？

有了前面的讲解，读者能猜到，计算机内部应该是一堆电路在飞速干活。这么想是正确的，计算机就是一个又笨又快的机器。通过简单的门电路基本的功能（加法移位逻辑运算）组合成威力无比的现代计算机。

读者可能厌倦了在这么基本的物理层面学习计算机编程，但是少安毋躁，虽然这很啰唆，但是值得的，最后花点时间从底层看看现代计算机是如何执行的。

现代计算机的理论模型是图灵机（Turing Machine），由Alan Turing在1936年的一篇论文中提出。读者可以从这个网址找到原始论文：www.cs.virginia.edu/～robins/Turing_ Paper_1936.pdf。

图灵机定义：M=(Q,E,Γ,δ,q0,B,F)

其中，Q是有限状态集，E是输入字母表，Γ是带符号集，δ是动作函数（L表示读写头向左移动一格，R表示读写头向右移动一格），q0（q0∈Q）是初始状态，B（B∈Γ）表示空白符，F（F⊆Q）是终止状态集。

许多读者看着这个就头大了，这里写出来也只是想让大家知道图灵机是得到了严格数学证明的东西。

Alan Turing是英国数学家，他奠定了理论计算机的基础，提出了判定机器是否具有智能的图灵测试，是计算机科学之父和人工智能之父。

下面来看看图灵机形象的表示。

这个概念机器简单到出人意料，更加出人意料的是这台机器就表示了人的最大可计算能力！

图灵机的组成部分如下图所示。

1）一个无限长的存储带，由一个个连续的存储格子组成，每个格子可以存储一个数字或符号。

2）一个读写头，读写头可以在存储带上左右移动，并可以读、修改存储格上的数字或符号。

3）内部状态存储器，该存储器可以记录图灵机的当前状态，并且有一种特殊状态为停机状态。

4）控制程序指令，指令可以根据当前状态以及当前读写头所指的格子上的符号来确定读写头下一步的动作（左移还是右移），并改变状态存储器的值，令机器进入一个新的状态或保持状态不变。

2.5.2 从101页报告到极简计算机

按照图灵的理论模型，设计计算机时要如何做呢？历史上有很多种尝试，伟大的数学家、物理学家冯·诺依曼在1945年写了一个报告“First Draft of a Report on the EDVAC”，报告中进行了一些规定，后来都是按照他的规定来做的，所以现代计算机体系也称为冯·诺依曼体系结构。这份报告总共有101页，史称101页报告（原文见http://archive.org/download/firstdraftofrepo00vonn/firstdraftofrepo00vonn.pdf）。

在这个报告中提出了现代计算机的结构，如下图所示。

冯·诺依曼体系结构规定如下。

1）程序和数据都用二进制数表示。

2）采用存储程序方式，指令和数据统一存储在同一个存储器中。

3）顺序执行程序。

4）计算机由运算器、控制器、存储器、输入和输出设备5部分组成。各个部分之间用总线（Bus）连接，用于传递数据。

这个结构有一个特点是程序与数据都是存放在存储器中（前面提到过，运算本身是0/1表示的，数据也是0/1表示的，它们从形式上具有同一性）。

现在的CPU就是由控制器、算术逻辑单元和寄存器组成的。

1946年造出来的第一台电子计算机如下图所示。

2.5.3 跟着“极简”执行代码

现在用一台极简计算机来执行一般代码。

这台极简计算机有一个控制器，它从指定的地址读指令，指令地址存在PC中，指令存在IR中。读完这个地址后，PC就加1，准备读下一条地址。控制器按照指令进行控制。

这台机器有一个算术逻辑单元ALU，它负责几个算术逻辑操作，如加、减、与、或、非、异或、移位等基本运算。操作的数据对象放在寄存器中。

这台机器有16个寄存器，用于存放运算过程中的数据。

这台机器有存储器，保存程序和输入的数据，通过8位地址确定指令和数据的位置。控制器从存储器读取指令，加载数据也回存数据。

起连接作用的总线这里没有画出来。

下面通过代码把这些功能描述出来，如加载数据，功能是从存储器的某个位置加载数据到寄存器，记为LOAD R0 M40，解释为从地址为40的内存中加载数据到0号寄存器中；加法记为ADD R0 R1 R2，解释为把1号寄存器的数据和2号寄存器的数据相加，结果放到0号寄存器中。

这台机器还要能停下来，所以需要给指令集增加一条特殊指令HALT。

为了便于统一处理，给这个操作进行编码，后面的操作数也规定统一的格式。比如规定一条指令由16位组成，分成四段，每段4位，第一段为指令段，后面三段表示操作数地址。把这台机器能做的事情列一个表格，叫作指令集，见下表。

这里尝试构建的这台计算机能执行12条指令。有些指令用不到三个数据段，可以默认给0。

有了这个可以编程了。以Python的一条语句c=a+b为例。

程序可以如下编写。

指令1，加载数据a（假设内存地址为40）到寄存器0。

指令2，加载数据b（假设内存地址为41）到寄存器1。

指令3，把寄存器0和寄存器1的数据相加，存到寄存器2。

指令4，把寄存器2的数据回存内存地址42中。

指令5，停机。

代码表示为：

用十六进制表示为：

把这个程序装载进计算机，按照冯·诺依曼体系结构，也是装载在内存中的，可以规定内存区域的开头64个地址为程序保留（十六进制地址编号为00-3F）。

先不管程序和数据是如何装载进去的，在装载好之后，内存中的内容如下图所示。

程序执行过程如下。

1）CPU初始化状态，PC设为00。

2）控制器读取00地址的指令，将1040读取到IR中，PC加1变成01。

3）控制器将IR中的指令1040译码为M40-＞R0（将40地址的数据加载到0号寄存器）。

4）控制器执行指令。

执行完这条指令后，这台计算机变成如下图所示。

以上三条为一个机器执行周期（取指令-译码-执行指令），不断地执行下去，直到遇到HALT指令。

这就是现代计算机的执行过程。学到这一步，终于看到了“庐山”真面目。之前学了那么多基础进行铺垫，一步一步辛苦叠加，“为伊消得人憔悴”，但是功夫不负有心人，最后在这里触摸到了编程知识的硬核。

这台机器能“跑”起来了，但是可以看到它缺少输入设备，没办法把程序和数据输入进去。这里不仔细探讨了，从原理上，这台机器已经可以运行了。如何把程序和数据输入进去是另一个课题，实际上只要把机电设备转换成电子信号的办法都可以，如键盘、鼠标、纸带。穿孔纸带如下图所示。

穿孔纸带的原理很简单，穿孔纸带上每个数据孔位上有一根金属针，下面有容器，里面装着水银。按下压板时，纸带上有孔的地方，针通过与水银接触，电路通，没有孔的地方针被挡住了，电路不通。这就把纸带上的0和1（有孔和无孔）转成了电信号。

那么程序和数据其实就是由纸带上的孔表示的，如规定有孔的地方为1，没有孔的地方为0。几十年以前的程序员就是这么编写程序的，用一个东西给纸带打孔（比起第一代程序员钻进计算机中连线已经进步很多了）。Debug可费劲了，需要用纸片把打错的孔糊起来。那个时候的程序员，还具有传统工匠的样子。

别小看这些，当年阿波罗登月时，控制程序就是用了很多卷纸的。阿波罗登月计划中，有一个职位叫“重量控制官”，是控制搭载物体的重量的，太重的东西不能携带。这个重量控制官就挨个部门跑，收集物品重量并记在小本子上，跑到程序部门，那个时候的人们对程序还没有什么概念，就问“你们部门搭载的程序有多重？”，程序员说没有重量，这个官员不信，认为凡是东西都会有重量的。过了三天，重量控制官又来了，这次手里抱了一大卷纸，跟程序员们说“你们的程序我称过了，35磅。”这些程序员用可怜的眼神看着重量控制官说“纸带不是程序，上面打的孔才是。”

现在了解了冯·诺依曼体系结构如何执行程序，这个体系有超过七十年的时间了，未来会如何发展？留给读者去想象。

对计算机内部的结构和执行过程就讲到此为止，这是一本编程书，可以跳出物理结构了，只关注概念逻辑，后面，只在算法和Python语言的层面来继续编写各种程序。

欢迎来到虚拟逻辑世界。