每周学点大数据 | No.5算法的分析之图灵机

灯塔大数据

发布于 2018-04-09 10:30:14

7560

发布于 2018-04-09 10:30:14

文章被收录于专栏：灯塔大数据灯塔大数据

No.5期

算法的分析之图灵机

小可：那计算机科学有没有对易解和难解问题进行一个相对严格的界定呢？

Mr. 王：有的，这里既然提到了多项式算法和易解难解问题，那么我们就简单来谈一谈NP完全性的问题，这有助于对后面一些问题的理解。真正的NP 完全性讨论和复杂度归约是比较复杂的主题，一般要到硕士生阶段才会接触，这里我们只简单谈谈。提到NP完全性，我们先要了解前面提到过的“图灵机”。

小可：我也很好奇，这个“图灵机”究竟是什么呢？

Mr. 王：想要理解图灵机，需要具有一定的自动机理论基础，最好先了解一下有穷自动机和下推自动机。这里我力图用浅显易懂的语言来解释它，所涉及的一些数学定义和形式化定义就暂且不提了。

简单来说，图灵机是由一个读写头和一条两端无限延伸的纸带构成的。当然，也可以是多个读写头和多条纸带，科学家们已经证明，单带图灵机和多带图灵机是等价的。这里我们先谈谈单带图灵机。

图灵机图片- 百度百科

其中读写头可以在纸带上左右移动，可以在纸带上写下符号，也可以将纸带上的符号擦去（或者说写下“空”这个符号），还可以读取纸带上的符号。在读写头的内部，有一些“状态”，在读取不同的符号或者移动时，读写头的内部可以进行状态转换，在下一个阶段时，读写头可以根据状态和读取到的符号决定如何移动、读、写。

小可：这还是有一点抽象。

Mr. 王：这样吧，我们来设计一个图灵机，来看看图灵机是如何工作的。

比如，想让图灵机解决2+3这个算术题，我们就去编一个加法计算器的图灵机程序。

对于图灵机来说，它的一切都是可以定义的。为了方便起见，我们不使用十进制或者二进制形式，而是用纸带上的1个“1”表示数字1，用2个“1”表示数字2，依此类推。

小可：这也就是说，只要在纸带上画几个“1”就可以表示几了。

Mr. 王：另外，我们还要用一个符号来表示加号。这里其实选用任何符号都可以，但在计算机中常常使用二进制形式，那么除数字1 以外就会用到数字0。为了方便起见，我们用数字0来表示加号。那么这个算式可以表示成什么？

小可：我们要计算的算式是2+3，那就是“110111”。

Mr. 王：很好，我们将它写在纸带上。为了让纸带上的空白区域更加方便地被图灵机识别，我们用字母B表示空白（blank）。

小可：由于纸带是无限长的，那么纸带上留下的就是……BBBB110111BBBB……。

Mr. 王：光有纸带还是不够的，还要对图灵机进行编程。我们先不去看图灵机程序，而是想一想，这应该怎么做？

小可：如果“11”表示2，“111”表示3，那么2+3的结果5就是“11111”。

Mr. 王：很好，这个思路是对的，我们需要做的其实就是将纸带上的110111变成11111。

当然，一个加法计算器不能只对2+3可用，它也应该可以把1011变成111，表示1+2=3 ；可以把11101111变成1111111，表示3+4=7。

小可：其实这好像也不难，只要把中间的0去掉，然后把右边所有的1都往左挪就可以了。

Mr. 王：很好，其实图灵机就是这样做的。不过还可以做一个小小的改进，让图灵机执行起来更加方便，当图灵机遇到0时，我们把它变成1，然后再把最后一个1抹掉，是不是也可以啊？

小可：嗯，这样和前面那种效果是一样的。

Mr. 王：好，我们用状态图来表示一下这个图灵机程序。

状态转移图

小可：这个好复杂啊。

Mr. 王：其实图灵机程序本质上就是读写头遇到了一个什么符号、如何转换状态、如何修改纸带上的符号、什么时候停机这样的一个组合，箭头连接符号用来表示状态的转换。上面的X/Y →表示读到符号X 时，将其改写为符号Y，并且读写头右移（相应的“←”就表示左移）。

我们来看看它的执行结果。

刚开始，图灵机读到B，根据转换图读写头向右移动：

遇到1，读写头右移，又遇到1，读写头继续右移：

读写头遇到0时，根据我们的设计，要将它改为1，然后右移：

同时，状态变为q1 ：

右面的1和左面的一样，继续让读写头右移跳过它们即可，然后继续右移：

继续右移，遇到了B，这时我们知道右边已经没有1了，但是前面还有一个1我们没有将其抹掉，也就是此时纸带上留下的计算结果比正确的结果要多1，根据程序继续执行，将其去掉。注意，此时状态要发生转换。想想看，如果没有一种状态记录读写头已经经过了扫描全部的1那个步骤的话，就会出现读写头返回去抹掉多余的1时遇到了1，根据状态q1上面的转换，又继续往右走，然后遇到B又返回的死循环情况。