图灵机 (第2/3页)
荷糖！太气人了！”
“……写了一晚上题目了，不要再聊题目了。”我叹着气说。
“嗯……好，不过还是再给我一颗薄荷糖。”
我们混在高二放学的人流中，零醛剥开糖纸把糖扔进嘴里“嘎嘣”嚼碎。
“要是有那种自动解题的程序就好了……”
“噗哈哈哈哈哈哈哈……解高中数学题的话说不定将来真的会有，但一般的数学命题……真可惜啊，不可能。”吃着糖的零醛好像恢复了一些活力，于是开始向我讲解奇怪的东西。
“你知道希尔伯特问题吗？”
“不太清楚……不过听说过他的名言，‘我们必将知道，我们终将知道’。”
“啊对，他在1900年提出过‘世纪之交待解决的23个问题’，其中一个——所谓的‘Entscheidungsproblem’——”她念着这个冗长的德语单词——“就是‘是不是对所有命题都有明确程序（definite procedure）可以在有限时间内告诉我们命题是真是假’。要是真能这样就好啦，什么哥德巴赫猜想黎曼猜想……只要把这些问题放进判定机器让他运行一下就能知道了。更早的时候莱布尼兹也有过类似的幻想，他自己制造了加法器和乘法器，并且觉得人类将来能建造出所有判断数学命题真假的机器。”
“好了好了我知道了……所以快点来打破我的幻想吧。”
“嗯……你要听听用图灵机的证明吗？”
“图灵机……是电脑吗？”
“只能说电脑算是一种通用图灵机啦。——图灵机是图灵构造的一种假想的机器，它有一个读写头，”零醛从口袋里掏出一支自动铅笔，戳了戳笔尖示意，“一根纸带，有很多格子，写着零和一，读写头在纸带上自由移动。”她将铅笔沿着手指前后移动,“机器还有一些内置的状态，它会根据当前所处的状态和读到的方格里的0或1来改变自己的状态、左右移动，或在当前的格子里写下和擦除记号。”她“咔哒咔哒”地按了按笔尾。
“给一根输入纸带，有的图灵机可以上面运行有限步后进入停机状态，有的则会一直运行下去——比如我可以造一台机器，在状态1下读到0或1都右移一格进入状态2，在状态2下读到0或1都左移一格进入状态1，进入“左移右移左移右移”的死循环……顺便说一下，通过一些编码，这些规则可以写成01纸带的形式，于是它们就既可以放在机器的脑袋里，也可以拿出来作为机器的输入。——这很重要！”她挥了挥自动铅笔。
我点了点头，表示能听懂。
“所以我们现在有一台图灵机——叫他小明吧。有一张输入纸带。我们就遇到了一个问题——能否在有限时间内通过明确的步骤判定小明在处理这条纸带时会不
（本章未完，请点击下一页继续阅读）