图灵机

写着零和一，读写头在纸带上自由移动。”她将铅笔沿着手指前后移动,“机器还有一些内置的状态，它会根据当前所处的状态和读到的方格里的0或1来改变自己的状态、左右移动，或在当前的格子里写下和擦除记号。”她“咔哒咔哒”地按了按笔尾。

“给一根输入纸带，有的图灵机可以上面运行有限步后进入停机状态，有的则会一直运行下去——比如我可以造一台机器，在状态1下读到0或1都右移一格进入状态2，在状态2下读到0或1都左移一格进入状态1，进入“左移右移左移右移”的死循环……顺便说一下，通过一些编码，这些规则可以写成01纸带的形式，于是它们就既可以放在机器的脑袋里，也可以拿出来作为机器的输入。——这很重要！”她挥了挥自动铅笔。

我点了点头，表示能听懂。

“所以我们现在有一台图灵机——叫他小明吧。有一张输入纸带。我们就遇到了一个问题——能否在有限时间内通过明确的步骤判定小明在处理这条纸带时会不会停机。

“先假设答案是‘能’——于是我们就会有一台特殊的图灵机——叫它‘检查员’吧，他只要左手拿着小明的纸带，右手拿着输入纸带——呃也可以把它们打印到一张纸带上，算了几张纸带不重要——就能判定小明对这个输入会不会停机。如果左右手都拿着小明的纸带，就能判定小明对自身的输入会不会停机。想象一下，比如说——这是一座机器人工厂，由于陷入死循环很麻烦，所以大家在运行纸带之前都要去让检查员判定一下能不能停机……挺好的，嗯哼？

“只是有一天，检查员出了点状况——无论是喝多了酒还是吃多了巧克力还是脑袋里飞进了一只虫子——总之，当小明对输入纸带不能停机时，生病的检查员照常在运行完这两条纸带后停下，给出‘不能停机’的结论；而当小明对输入纸带能够停机时，生病的检查员自己在处理这两条纸带时却进入了死循环，其他机器不得不把他强行从纸带上扯开。场面一度失控。

“所以生病的检查员想给自己作个检查。

本章未完，请点击下一页继续阅读！ 第4页 / 共6页