Liam W
封面

通俗算法03 - 人人都能懂的图灵机原理

作者
王亮·发表于 3 年前

上一讲我们知道了图灵机在历史上出现的原因,它是一个计算模型,用来判定一个问题到底可不可解,那么它是如何判定的呢?

在本篇文章开始之前,我们先来看一段视频:

点击这里观看

图灵机的构成

为了方便讲述图灵机的构成,我从视频中截取了一张图:

图灵机的组成

视频中的图灵机是用现代工艺做的,可以看到图灵机并不复杂,它做的事情很简单。当机器处于“Read”状态的时候,会从纸带上读内容,完了经过某种计算再向左或向右移动,然后在当前位置写上符号 0 或 1(如果已经有符号会先擦除),下面有个状态(State)会变化,另外还显示了当前的位置(Position)和步数(Step)。

从上面图中我们可以看到,图灵机就是一个机器(称为控制器)和一根纸带组成的。

控制器,包含用来写内容的“笔”、“擦子”。它可以向纸带读、写、改数据,所读内容我们可以理解为程序语句;它可以使纸带左右移动;它还有一个可以变换的状态。

纸带,左右两边无限延长,纸带上可以写内容(也就是存储),内容可以是数字和字母。我们可以把纸带理解为存储器。

我们再来看看图灵机是怎么工作的。

图灵机运行原理

首先图灵机工作前,需要先在纸带上写好一些符号,例如“1 1 0”:

加粗的方格表示当前控制器笔头指向的位置。现在我们编写一段简单的程序,这段程序用表格表示是这样的:

读取写入移动
空白
01向右移
10向右移

这个程序很容易理解,比如表格的第三行(即最后一行),意思就是当程序读取到 1 时,在当前位置写入 0,再向右移动一格。假设我们已经把这段程序输入到机器中了,然后机器开始运作。

首先机器读取纸带当前的符号,如上面的纸带图,读取到的是“0”,匹配程序表的第二行,按照程序的指示,应该在当前位置写入“1”再向右移一格,过程如下两个纸带图所示:

机器继续读取当前位置的符号,读取到的是“1”,匹配程序表的第三行,然后按照程序的指示在当前位置写入“0”,再向右移一格,这一步图示如下:

依此继续执行,最后一步图示如下:

最后读取到空白时,按照程序的指示,既不写也不移动。事实上这个程序并不完整,还存在问题,例如怎样才能让机器停止,又如何让机器不停地重复读取、写入和移动的过程呢?

我们还要在程序中加入状态,控制器必须要有记录状态的功能。为什么一定要加入状态呢?因为如果没有状态的话,在纸带有限的符号下,程序表只能是有限的行数。比如示例中的纸带有三种符号:0、1 和空白,那么程序表最多也就只能是三行,机器最多只能执行三种可能的动作。加入状态后,假如状态有 0 或 1 两种,那么程序表的行数就可以增加到 2x3=6 行,这称为 3 符号 2 状态图灵机。

例如下面是一个含有两种状态的程序表:

当前状态读取写入移动修改状态
0空白空白向左移1
001向右移1
010向右移0
1空白空白向右移停止
101向左移1
110向左移1

机器每一步需要结合当前的状态再来执行相应的操作,所以在机器运行前,需要有个初始状态。机器执行完一步后,按照指示修改状态,以备下一步使用。

假如机器的初始状态为 0,继续使用上面最后一步的纸带,当前指向的是空白,那么匹配的是表格的第一行,按照程序指示,在当前位置写入空白,并向左移一格,图示如下:

依次类推,后续步骤的图示如下:

一步步这样匹配演示下来,上图对应的最后一步是向左移一格后指向了空白,状态变为了 1(匹配的是第五行)。此时,继续执行,当前位置是空白,当前状态是 1,那么匹配的是表格的第四行,向右移一格,状态变为停止,如下图示:

这样图灵机就完成了一次计算。纸带由“001”通过给定的程序计算变成了“110”,如果把它们看成二进制的话,其实是做了一次 1+5=6 的运算。

随着控制器状态增多,那么我们就可以编写越复杂的程序,也就能和现代计算机一样执行复杂的算法。

好了,知道了图灵机的运行原理,我们再回到开篇提到的问题,既然说图灵机是一种计算模型,那么它怎么来判定一个问题有没有解呢?

图灵机停机

如果图灵机成功完成了一次计算,我们就说图灵机成功停机了。停机就意味着计算结束并得出结果,停机后纸带上的符号就是计算结果。

当我们遇到一个问题,比如说输入 A,问:能否由 A 计算出 B?图灵机能帮我们做一个判定,如果我们能在 A 与 B 之间找到或设计出一个图灵机程序,使输入 A 停机得到的结果是 B,就说明这个问题可解,否则就说明这个问题不可解。

图灵机就是这样解决“可计算性的判定”问题的,这是图灵机的一个重大意义。另外,我们可以看到图灵机给出了一个可实现的通用计算模型,还引入了存储器、程序、控制器等概念的原型,为现代计算机奠定了基础,这也是图灵机为什么受到人们重视的原因。

参考:

https://www.cl.cam.ac.uk/projects/raspberrypi/tutorials/turing-machine/one.html