第三中文网

图灵机（第3页）

“给一根输入纸带，有的图灵机可以上面运行有限步后进入停机状态，有的则会一直运行下去——比如我可以造一台机器，在状态1下读到0或1都右移一格进入状态2，在状态2下读到0或1都左移一格进入状态1，进入“左移右移左移右移”

的死循环……顺便说一下，通过一些编码，这些规则可以写成01纸带的形式，于是它们就既可以放在机器的脑袋里，也可以拿出来作为机器的输入。

——这很重要！”

她挥了挥自动铅笔。

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

“所以我们现在有一台图灵机——叫他小明吧。

有一张输入纸带。

我们就遇到了一个问题——能否在有限时间内通过明确的步骤判定小明在处理这条纸带时会不会停机。

“先假设答案是‘能’——于是我们就会有一台特殊的图灵机——叫它‘检查员’吧，他只要左手拿着小明的纸带，右手拿着输入纸带——呃也可以把它们打印到一张纸带上，算了几张纸带不重要——就能判定小明对这个输入会不会停机。

如果左右手都拿着小明的纸带，就能判定小明对自身的输入会不会停机。

想象一下，比如说——这是一座机器人工厂，由于陷入死循环很麻烦，所以大家在运行纸带之前都要去让检查员判定一下能不能停机……挺好的，嗯哼？

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

场面一度失控。

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

他左右手都拿着自己的纸带，想看看自己对自己的输入会不会停机——然后就出现了矛盾。”

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

“所以由反证法，检查员这样的机器不会存在。

——或者，如果你一定要问他怎样了的话——被自己的读写头与纸带摩擦所产生的热量焚毁殆尽了吧。”

我叹出一口气。

“希尔伯特还提出了其他的问题，比如数学是不是完备的——是不是所有数学命题都可以用一组有限的公理证明或证否；数学是不是一致的——是不是可以证明的都是真命题。”

“——这个命题是假命题！”

“哈，挺聪明的。

之后哥德尔证明了如果算术系统一致那它就不完备——诶几点了？”

我抬头看了下学校门口电子屏上的大钟，九点三十，我们已经在校门口的秋风中站了将近一刻钟。

“……我们是图灵机吗？”

我问了最后一个问题。

“谁知道呢，不过我觉得是的。”

“但我还没听说过谁的大脑因为接收了什么奇怪的输入而陷入不可预知的死循环……”

她不置可否地咧咧嘴。

到了要分别的路口。

她向左，我向右。

该奔向车站了，别误了末班车。

转身之前零醛停下了脚步，“哥德尔在天堂碰见了图灵，他说：‘看吧，果然有人要毒死我们！

’”

她说道，然后发出几声上气不接下气的笑。

怎么了？我回头担心地望着她，她摇摇头，抬眼凝视着我，然后又恢复了平日的微笑：

“没什么，t’&bp;a&bp;joke.”

一点也不好笑。