图灵机（2 / 3）

“it’sajoke！”她学着《生活大爆炸》中谢尔顿的语气，潜台词好像在说“真是个大笨蛋”。

“那，我们跑快点，就不冷了。”

“不要。”她突然拉住我的袖子。

“一起走。慢点走。”她轻轻地，用微微颤抖的声音请求。

“随堂测的第一条大题我忘记写空集的情况了……”

“我今天才……所以我讨论了半小时，结果发现题目说‘正整数’！啊快点再给我一颗薄荷糖！太气人了！”

“……写了一晚上题目了，不要再聊题目了。”我叹着气说。

“嗯……好，不过还是再给我一颗薄荷糖。”

我们混在高二放学的人流中，零醛剥开糖纸把糖扔进嘴里“嘎嘣”嚼碎。

“要是有那种自动解题的程序就好了……”

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

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

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

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

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

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

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

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

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

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