计算机发展史之图灵机

大家都知道计算机是可以完成运算的。那大家知道以前的计算机是怎么样完成运算的吗？今天我们就来讲解一下，以 图灵机和纸带来讲解。

根据维基百科解释，图灵机包括以下四个部分：

1. 一条无限长的纸带TAPE。

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

2. 一个读写头HEAD。

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

3. 一套控制规则TABLE。

它根据当前机器所处的状态以及当前读写头所指的格子上的符号来确定读写头下一步的动作，并改变状态寄存器的值，令机器进入一个新的状态，按照以下顺序告知图灵机命令：

    （1）写入（替换）或擦除当前符号；

    （2）移动 HEAD， 'L'向左， 'R'向右或者'N'不移动；

    （3）保持当前状态或者转到另一状态

4. 一个状态寄存器。

它用来保存图灵机当前所处的状态。图灵机的所有可能状态的数目是有限的，并且有一个特殊的状态，称为停机状态。

注意这个机器的每一部分都是有限的，但它有一个潜在的无限长的纸带，因此这种机器只是一个理想的设备。图灵认为这样的一台机器就能模拟人类所能进行的任何计算过程。

然后我们来说一下图灵机如何进行运算的，要让图灵机进行运算，首先要准备如下操作：

    （1）纸带上的符号初始化，如果计算，肯定要初始化数据，纸带上的1和 0 就是初始化的数据。

    （2）设置好图灵机控制器的当前状态

    （3）把读写头放置于开始的位置

    （4）放入对应的工作程序到图灵机，比如加法就放入加法的工作程序

5. 启动图灵机

图灵机开始运作之后，就会读取纸带上的符号和当前正在执行程序，来写入或者擦除纸带的相对应的符号，并且根据程序的指令，移动纸带，直至机器成功停机，计算也就完成了。

讲到这里相信大家肯定还是不太清楚，我们来图片说明一下把：

在工作程序中，一共有五条指令，这五条指令都是一样的。前两项为条件。后三项为操作。

解释一下没有讲到的符号：B=0（也就是空），R=向右移动一格，L=向左移动一格，H=位置不动。

当机器开始执行：获取到纸带上第一格的数据，为1，然后当前状态为q1，我们来匹配，就匹配到第一条指令语句，然后就执行后三项操作，当前格写入1，纸带右移一格，把当前状态变为q1。就这样一直执行下去，直到机器停止。

下面来看执行过程：

到了最后一步，我们发现状态为q3，读取到数据为空（b），匹配第五条指令，第五条指令执行操作，把当前格写入b（也就是空），

然后位置不动，状态为q3.这样每次都匹配到的是第五条，这样机器就停机了，计算也就完成了。纸带上的数据也就是计算的结果。大家可以根据初始数据和这张结尾数据。看出来这是个什么运算吗？

这就是计算机的计算原型，结尾附上图灵机操作过程的视频链接。

图灵机: