图灵机是什么？一起来看看它的工作原理

前言

当前的人工智能实际上还是属于数学问题的范畴，人工智能的发展也需要数学的理论支持。我们在讨论人工智能时本质上是在讨论可计算问题，著名的邱奇-图灵论题（Church–Turing thesis）表明一切可计算问题都可以使用图灵机来模拟计算，该理论由美国数学家邱奇和英国数学家图灵共同提出的。图灵所提出的图灵机本质是一种计算模型，计算针对的是确定性的事情，而不定的事则超出了计算的范围。

计算的分解

图灵认为任何可计算的问题都可以使用图灵机来模拟，对于某个可计算问题，我们根据一组确定的规则就可以通过移动纸带来得到问题的解，这组规则规定了如何在纸带上读写和移动。越复杂的问题需要的纸带就越长，同时我们可以将纸带看成是无限长的。图灵在构想图灵机时思考如何抽象一个计算过程，他思考着如何通过一个模型来描述计算的一般过程，那个年代的计算人员会在一张纸上通过数字和运算符号进行计算。图灵将这个在纸上的计算过程想象成在一条很长的纸条上，长纸条被划分成很多个方格，计算就在这些方格中进行。以乘法计算为例，如果我们要人工计算12×11的结果则一般会通过竖式进行计算，这种竖式就可以通过长纸条的方式来描述，计算方式不同但本质却是不变的。

乘法例子

将整个运算过程变成一条长纸条后我们需要关注的是纸条上不同位置的数字，这就好比有一个指针在纸条上移动读取纸带的内容，同时还会将一些运算结果写到纸带上。而对数字的具体运算操作则由计算人员来决定，比如是要相乘还是要相加。根据上述思路我们再看前面12×11的例子，首先是分别读取1和2执行1×2运算并将结果写回纸条中，然后分别读取1和1执行1×1运算并将结果写回纸条中，以上步骤组成的中间结果为12。同样地，对11的十位数进行类似操作并将结果写回纸条中，中间结果为120。

现在继续对两个中间结果进行计算，此时要做的是加法运算，这个操作可以看成是由计算人员的思维状态所决定的。分别读取两个中间结果的个位、十位和百位并进行相加，然后分别写回纸条中，它们组成的最终结果为132。

图灵机

下面我们详细介绍图灵机的组成结构和工作机制。一个图灵机包含了四个部件：一条很长（可以看出无限长）的纸带、一个能读取和修改纸带内容的机器人、机器人的内部状态（所有内部状态的值都属于“有限状态集”，比如图中的S1/S2/S3/S4/S5/S6）以及一个用于控制机器人移动的“固定程序”。

图灵机的大致工作流程为：机器人读取纸带上当前方格的符号，然后结合自己的内部状态去查找“固定程序”，接着根据“固定程序”的规则将输出信息写到纸带方格上并转换自己的内部状态，最后机器人进行移动，然后又在新的位置按上述过程不断往下执行。可以看到核心是“固定程序”，它指明了每种内部状态下遇到纸带上符号时应该如何进行操作，这些操作包括修改纸带当前格内容、机器人向左或向右移动一个方格、机器人内部状态的切换。

图灵机

假设机器人当前的内部状态为s，机器人读取到的当前格子的符号为x，“固定程序”指明应先将当前格子的符号改为y（不改动用&表示），然后将机器人内部状态改为q，最后移动机器人（向右移动一格用→表示，向右移动一格用←表示，不移动用@表示）。那么我们就能用一个五元组来表示图灵机的每个执行操作，比如(s,x,y,q,→)、(s,x,&,q,←)和(s,x,y,q,@)等等。

固定程序就是由有限个五元组来描述的，为方便大家理解我们绘制了如下的固定程序表，每一行都可以看成是一条规则。每个时刻的内部状态和当前格子符号是已知的，根据它们的值去查找固定程序表中的规则，然后就知道如何更新当前格子和内部状态，以及如何移动机器人的位置。

固定程序表

假设有一张“1101”纸带，机器人初始内部状态为S1，那么它的运行过程为：刚开始机器人读取到当前格子符号为1且内部状态为S1，此时符合固定程序表中的第一条规则，需要将当前格子符合和内部状态分别改为0和S2，然后向右移动一格。此时符合固定程序表中的第三条规则，需要将当前格子符号和内部状态分别改为0和S3，但不改变机器人的位置。此时符合固定程序表中的第六条规则，需要将内部状态改为S6但不改变当前格子符号，然后向右移动一格。

纸带运行过程

本公众号专注于人工智能、读书与感想、聊聊数学、计算机科学、分布式、机器学习、深度学习、自然语言处理、算法与数据结构、Java深度、Tomcat内核等。

作者简介：笔名seaboat，擅长人工智能、计算机科学、数学原理、基础算法。出版书籍：《Tomcat内核设计剖析》、《图解数据结构与算法》、《人工智能原理科普》、《图解Java并发原理》。