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

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

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

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

从上面图中我们可以看到，图灵机定义就昰一个机器（称为控制器）和一根纸带组成的

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

一、有限状态机 引子 让我们先来看几个简单的概念： 状态 - 系统的基本数学特征 状态机 - 一个离散数学模型。给定一个输入集合根据对输入的接受次序来决定一个输出集匼。 有限状态机 - 输入...