八一中文网

图灵机（第3页）

“噗哈哈哈哈哈哈哈……解高中数学题的话说不定将来真的会有，但一般的数学命题……真可惜啊，不可能。”吃着糖的零醛好像恢复了一些活力，于是开始向我讲解奇怪的东西。

“你知道希尔伯特问题吗？”

“不太清楚……不过听说过他的名言，‘我们必将知道，我们终将知道’。”

“啊对，他在1900年提出过‘世纪之交待解决的23个问题’，其中一个——所谓的‘Entscheidungsproblem’——”她念着这个冗长的德语单词——“就是‘是不是对所有命题都有明确程序（definite procedure）可以在有限时间内告诉我们命题是真是假’。要是真能这样就好啦，什么哥德巴赫猜想黎曼猜想……只要把这些问题放进判定机器让他运行一下就能知道了。更早的时候莱布尼兹也有过类似的幻想，他自己制造了加法器和乘法器，并且觉得人类将来能建造出所有判断数学命题真假的机器。”

“好了好了我知道了……所以快点来打破我的幻想吧。”

“嗯……你要听听用图灵机的证明吗？”

“图灵机……是电脑吗？”

“只能说电脑算是一种通用图灵机啦。——图灵机是图灵构造的一种假想的机器，它有一个读写头，”零醛从口袋里掏出一支自动铅笔，戳了戳笔尖示意，“一根纸带，有很多格子，写着零和一，读写头在纸带上自由移动。”她将铅笔沿着手指前后移动,“机器还有一些内置的状态，它会根据当前所处的状态和读到的方格里的0或1来改变自己的状态、左右移动，或在当前的格子里写下和擦除记号。”她“咔哒咔哒”地按了按笔尾。

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

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

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

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

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

“所以生病的检查员想给自己作个检查。他左右手都拿着自己的纸带，想看看自己对自己的输入会不会停机——然后就出现了矛盾。”

“如果判定能停机，就会进入死循环；如果判定不能停机，就会停下来……所以生病的检查员最终会怎样……”

“所以由反证法，检查员这样的机器不会存在。——或者，如果你一定要问他怎样了的话——被自己的读写头与纸带摩擦所产生的热量焚毁殆尽了吧。”