一起了解大名鼎鼎的“图灵机”

1936年，英国数学家阿兰・麦席森・图灵(1912―-1954年)提出了一种抽象的计算模型——图灵机( Turing machine)。图灵机，又称图灵计算机，即将人们使用纸笔进行数学运算的过程进行抽象，由一个虚拟的机器替代人类进行数学运算。

图灵提出的著名的图灵机模型为现代计算机的逻辑工作方式奠定了基础。

01

—

概念

图灵机是由英国数学家图灵在一篇论文《论数字计算在决断难题中的应用》（《On Computable Numbers, with an Application to the Entscheidungsproblem》）中提出的一种理想机器，这种机器可以通过一些简单的、机械的步骤模拟人类的一切数学运算。

“图灵机”设想有一条无限长的纸条，纸条上有一个个方格，每个方格可以存储一个符号，纸条可以向左或向右运动。这个纸带就像我们现代的计算机的存储器一样，纸带上面的每个格子是可以被读写的，在图 31这个例子里，机器只能写0、1、或者什么也不写。这个机器就是包含3种信号的图灵机（3-Symbol Turing machine）。

图1 图灵机设想的无限长纸袋

图灵机可以做下面三个基本的操作：

(1). 读取指针头指向的方格内的内容；

(2). 修改方框中的字符或者直接擦除方格内的内容；

(3). 将纸带向左或右移动，以便修改其临近方框的值。

02

—

一个简单的例子

一个简单的例子：这个例子实现的功能在纸带上打印“110”。如下面的图中所示，其中黑色框表示探头所在的位置。具体步骤为：（1）探头写1；（2）把纸带向左移动一格；（3）探头写1；（4）把带子向左移动一格；（5）探头写0。

图2 在图灵机的无限纸带上打印“110”示意

03

—

一个简单的程序

上面的例子比较简单，我们再来看一个稍微复杂点的例子。我们利用图灵机的设计思路设计一个可以执行“状态反转”的程序，即将前面打印在纸带上的“110”每个位上的二进制取反变成“001”。

这个时候我们需要预先定义一个指令集，也就是当图灵机上的探头读到方格内的内容时可以查这个指令集，然后将读取到的内容和指令集进行比对，根据指令集上的指示来进行下一步的操作。我们将这个简单程序的指令集定义为下表所示。

表1 指令集表

那我们看一下图灵机如何实现这个“状态反转”的小程序。如图2，探头读到的格子里的值是“0”，再查上面的表1的第2行，知道当读到“0”时，探头在格子里写入“1”，然后右移一格。

图3 探头读到“0”后的操作

此时，探头读到“1”，通过查指令集表 31，探头写入“0”，然后右移。如图4.

图4 探头读到“1”后的操作

上一步操作之后，探头再次在格子中读到“1”，再次查指令集表1，探头写入“0”然后右移。如图5.

图5 探头又读到“1”后的操作

经过上一步的右移之后，此时探头读到的格子里面的内容是空，通过读指令集表 31知道，探头不向格子中写入值，纸带也不移动。至此，图灵机就把“110”改写成了“001”。

机器状态：上面程序的指令集是不完整的，因为到最后探头不右移纸带也不改变格子里的值，但它还在不停的读取格子里的值然后查表。这个机器会一直重复执行命令，它并不知道何时停止执行。我们还需要引入一个机器状态（Machine State）的概念。我们给表 1增加一列。

表2 插入机器状态后的指令集

有了机器状态列的表 2，在上一小节中最后探头读到一个空的格子后，就会停止。

如果我们把方格里面的状态从“1”、“0”、“空”三种继续增加，而相对应的指令集表 32的行数也会跟着增加。这样的话，我们的图灵机就可以通过简单的读单元格、查指令集表、改变单元格状态、移动纸带这些非常简单、基本的操作来进行非常复杂的数学运算了。

我们现在使用的各种计算机、嵌入式系统等虽然看似复杂，但在本质上也还是对图灵机的进化而已。