人人都能懂的图灵机原理

Love The Way You Lie 2022-11-10 01:19 253阅读 0赞

# 人人都能懂的图灵机原理 #

图灵机是一个计算模型，最早用来解决判定一个问题到底可不可解，那么它是如何判定的呢？

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

[ https://www.zhihu.com/zvideo/1287337736785944576][https_www.zhihu.com_zvideo_1287337736785944576]

## **图灵机的构成** ##

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

![560a01510deb0706836deb821ed28375.png][]

![d01bae60431bf4840ac009226db3a60c.png][]

[![762ccf30799d96954de18465c2984c30.png][]][https_www.zhihu.com_zvideo_1287337736785944576]

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

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

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

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

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

## **图灵机运行原理** ##

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

![f496dc86e3877b75bb73251a4ea17514.png][]

![232939113ca26ea01eea298fc84118c4.png][]

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

![7e574ac60bd9bb30e19700979d25bb98.png][]

![ed39c711ad32c907b5be3bf11071b967.png][]

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

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

![1e83c53324ad46237d9707f520024a0a.png][]

![bcf92ee4bf3cdebf48658aa3237774a0.png][]

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

![afe634755fd78e1c487080f7c4d8958e.png][]

![da6527d33b9ee3776884ed3d3b60719f.png][]

依此继续执行，最后一步图示如下：

![0d48aac2b0d0a92828a61654c9e95d29.png][]

![cea888b80bc230c410bcc8f9b02a1c5e.png][]

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

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

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

![b59374e8c42d7b70b3674a25ac7c7854.png][]

![4ca7065ea3fdd7fcbfff905eb8eb5deb.png][]

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

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

![9ad97df240e92c8d49e0893912aac20e.png][]

![77d977fb7cae4c7cfe9aefd10a966d44.png][]

依次类推，后续步骤的图示如下：

![49dbdb1ca04876e2f5c3463330fac097.png][]

![b84f31f688e99b7ca1ea9027c0c06ee8.png][]

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

![7a9fd58b82b132b174b3b80cfc1b7c37.png][]

![bd78cc02055307a0330b51be81b8d249.png][]

这样图灵机就完成了一次计算。纸带由“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][https_www.cl.cam.ac.uk_projects_raspberrypi_tutorials_turing-machine_one.html]

[https_www.zhihu.com_zvideo_1287337736785944576]: https://www.zhihu.com/zvideo/1287337736785944576
[560a01510deb0706836deb821ed28375.png]: /images/20221023/4170895bf9624183a7e070cd0326b44e.png
[d01bae60431bf4840ac009226db3a60c.png]: /images/20221023/3ea5141bb96d4df1b115668eccb78795.png
[762ccf30799d96954de18465c2984c30.png]: /images/20221023/c9ac8802cdbe4d55840be6800681cb48.png
[f496dc86e3877b75bb73251a4ea17514.png]: /images/20221023/25ad6e06673b44cba84e8b446afc93dc.png
[232939113ca26ea01eea298fc84118c4.png]: /images/20221023/948ee6e1369f43ee87cfb3d112d148fc.png
[7e574ac60bd9bb30e19700979d25bb98.png]: /images/20221023/81489db4f3c74afea1b06af0d4ace60f.png
[ed39c711ad32c907b5be3bf11071b967.png]: /images/20221023/f4112df9c7284df5bce8ee959b49e3f7.png
[1e83c53324ad46237d9707f520024a0a.png]: /images/20221023/c5be527bb7f84d808573fe3785e761a2.png
[bcf92ee4bf3cdebf48658aa3237774a0.png]: /images/20221023/4ef44b7cca4141379091fe2390689715.png
[afe634755fd78e1c487080f7c4d8958e.png]: /images/20221023/941ecd9f7064483b810539982e2ee108.png
[da6527d33b9ee3776884ed3d3b60719f.png]: /images/20221023/bed67c9a216c4d3ea0d6689633a452de.png
[0d48aac2b0d0a92828a61654c9e95d29.png]: /images/20221023/a00e9a23c7f4456f93d1c0dad97ab429.png
[cea888b80bc230c410bcc8f9b02a1c5e.png]: /images/20221023/5642c633b2dc4b2aac2795d2e6756edb.png
[b59374e8c42d7b70b3674a25ac7c7854.png]: /images/20221023/99fe2df9a4234fb1804993cf99db9278.png
[4ca7065ea3fdd7fcbfff905eb8eb5deb.png]: /images/20221023/c69d53a1f7b34f37a5d59ad39702a581.png
[9ad97df240e92c8d49e0893912aac20e.png]: /images/20221023/cbb4de3a32544c5d9049a2641c5169ed.png
[77d977fb7cae4c7cfe9aefd10a966d44.png]: /images/20221023/970ebb7bc21a46f297988c0273338a10.png
[49dbdb1ca04876e2f5c3463330fac097.png]: /images/20221023/85f793119e414f69aa88039d62036e47.png
[b84f31f688e99b7ca1ea9027c0c06ee8.png]: /images/20221023/7777f30c7a0742eab23b2071aca155d1.png
[7a9fd58b82b132b174b3b80cfc1b7c37.png]: /images/20221023/73fb0dad6f2f4028bad35340a0781a5e.png
[bd78cc02055307a0330b51be81b8d249.png]: /images/20221023/f90296d73a7a403680967122120e5ef9.png
[https_www.cl.cam.ac.uk_projects_raspberrypi_tutorials_turing-machine_one.html]: https://link.zhihu.com/?target=https%3A//www.cl.cam.ac.uk/projects/raspberrypi/tutorials/turing-machine/one.html