|
撰文 AATISH BHATIA 编译 张竞文 赵维杰 微信、手机QQ搜索关注 DuoDaaMath 每获得更多数学趣文 计算机可以驾驶汽车，可以控制火星探测器登陆，还可以在《危险边缘》智力问答节目里击败人类......但是，有没有什么事情是计算机永远都做不到的呢？ 计算机当然会被它们的硬件所限制，比如我的智能手机，（暂时）并不能同时当电动剃须刀用。但是这些只是物理上的限制，如果我们一心想做，总是能够克服的。所以让我把问题描述得更准确一点：有没有什么计算机永远无法给出解答的问题？ 当然了，现在有很多问题计算机都很难给出解答。例如，在学校，我们会学习因数分解（30 = 2 × 3 × 5, 42 = 2 × 3 × 7），小孩子们都知道要按照一个简单的程序去进行计算。但是对巨大数字进行因数分解并不容易，直到2007年，如果有人能对以下的数字进行因数分解，就能得到十万美元的奖金。这个数字是：
不仅如此，直到2014年，没有一个人公开宣布自己解决了这个问题。这不是因为我们不知道解决问题的方法，仅仅是因为要花太长时间而已。我们的计算机太慢了。（事实上，正是因为计算机难以处理这些天文数字，互联网加密算法才成为可能。） 所以，如果想将当代科技水平的影响去除在外，我们可以重新描述这个问题： 出人意料的是，这样的问题确实存在。“停机问题”想知道的，是一个计算机程序会在一段时间后停止运行，还是会永远运行下去。这是个很实际的问题，因为无限循环是一类很常见的 bug，经常不动声色地出现在某人的代码里。在1936年，一位强大的数学家兼密码破译学家，艾伦·图灵就已经证明：让一台计算机检查你输入的全部代码，然后准确地告诉你这串代码会不会陷入无限循环是不可能的。换句话讲，图灵证明了：对于计算机而言，停机问题永不可解。 你也许经历过这样的场景：你正在复制文件，然而进度条突然不动了（经常是停在了99%）。你要等多久才会放弃呢？你怎么才能知道，它是永远都不会前进了，还是，哪怕在几百年后，会终于完成你文件的拷贝呢？用计算机学家 Scott Aaronson 的类比来说：“如果你和你朋友打赌说你的表永远不会停，要等到什么时候你才能宣告胜利呢？” 受够了对进度条的持续等待之后，你就会想：如果能有人写出一个调试程序，搞定所有这些烦人的 bug，那该有多好啊！不管是谁，如果真的写出了类似的程序并卖给微软，他肯定会赚钱到手软。但是在你兴冲冲地自己去开发软件之前，还是要注意一下图灵的建议——一台计算机不可能检查代码并给出它是否会停止运行的靠谱结论。 这是一条异常坚定的断言：图灵在讨论的不是当前科技的界限，而是对于计算机能做什么提出了一项基本的限制。现在不行，2450年还是不行，现在不行，未来也永远不行。计算机永远无法解决停机问题。 在他的论证中，图灵首先要在数学上定义我们通常所说的计算机和程序。当基础工作完成之后，他就可以用屡试不爽的反证法给出最后一击。在理解图灵的论证过程之前，我们先来热热身，思考一下更简单的“说谎者悖论”。想象有人告诉你“这句话是错的”，会怎样？如果这句话是对的，那么联系这句话的内容，它明显是错误的。同样，如果这句话是错的，那么它事实上已经准确地描述了自己，所以一定是正确的。但是它不能同时是正确的和错误的——矛盾就这样产生了。这种通过自我指涉形成矛盾的思想正是图灵的论据的精髓。Scott Aaronson 是这样介绍它的：
“就像是一条猎狗终于追到了自己的尾巴并且吞掉了自己，那台神秘的机器在矛盾中消失了。”Photo: Michael Holden/Flickr 接下来，就让我们看看图灵对于“计算机永远无法解决停机问题”的论证过程，看看我们到底为什么永远不可能编写出进行“死循环检测”的程序。 假设存在一个可以判断任意程序（比如程序 A）是否会停机的程序 P：当 A 会停机时，P 的输出值 P(A) 为“good”；当A不会停机（或者说A会陷入死循环）时，P(A) 为“bad”。 在 P 的基础上，我们可以构建程序 Q：当 P 的输出值为“good”时，Q 将不会停机（陷入循环）；而当 P 的输出值为“bad”时，Q 将停机。 下面的表格可以概括 P 和 Q 的运行原理： 那么，当我们用 P 来判断 Q 是否会停机时会发生什么呢？将输入程序 A 替换为 Q，上面的表格就变成了： 第一行和第三行中出现了截然相反的内容：如果 Q 会停机，则 P(Q)为 good，那么 Q 将不停机；如果 Q 不会停机，那么 P(Q)为 bad，所以 Q 将停机。 换句话说，我们构建出了一个无法由 P 准确判断其是否会停机的程序 Q。所以，能够判断任意程序是否终将停机的程序 P 不存在。 为表达对图灵的纪念，语言学家杰弗里·普勒姆仿照苏斯博士的风格写作了一首诗，用这首诗来呈现图灵的上述论证过程。苏斯博士被认为是二十世纪最卓越的儿童文学家和教育学家，他独具一格的诗作《戴帽子的猫》获得了无数读者的喜爱。经普勒姆允许，我将全诗抄录（试译）如下： 对循环检测程序的检测 关于停机问题不可解的一项证明 Geoffrey K. Pullum 没有程序能替你捉虫。 这不只是断言，我要证明给你看： 即便你的努力不息不止， 也算不出程序是否会终止。 想象你有一个程序 P， 它能将任意程序记心里， 看透源代码，挑出所有问题， 经过分析告诉你，程序是否陷入循环里。 你输入了程序，填入了数据， 于是 P 开始工作，我们一起等一会儿， （有限的计算时间过后）正确结果显现， 告诉你无限循环是否会出现。 无限循环不出现，P 就输出“好” 说明程序会停机，正如 P 所料。 倘若出现死循环， P 就输出“糟”——你的程序一团乱。 然而我会告诉你，根本没有这个 P， 你若给我一个 P， 我就还你一道逻辑题， 保你立场尽失，大脑宕机。 以下是我的小把戏——操作起来并不难。 我要构建一个程序 Q， 用它调用程序 P， 由此带来大混乱。 给定一个程序 A， 我们让 Q 开始第一步， 调用 P 来判断 A， 看 A 是否会循环。 如果 P 回答说“糟”，Q 就当场被停掉。 如果答案正相反，Q 就回头再一遭， 回头一遭再一遭，陷入无限循环大监牢， 再难停机到地老。 程序 Q 也别想跑； 它是跑是停也要考一考。 当它自己考自己，结果究竟会怎样？ 循环与否你来想： 如果 P 说 Q 不停，Q 就马上被停机； 那么 P 的判断不合理！ 如果 Q 它会停机，所以 P 它说了“好”， 那么 Q 将进入死循环！（P 的预测成玩笑） 无论 P 的判断是怎样，都给 Q 的找茬留余地： Q 利用 P 的输出让 P 像儿戏。 不管 P 有多努力，Q 的结果它还是难捉摸： P 正确的时候会出错，出错的时候才能对！ 我制造了一个小悖论，下面的概括让它变简洁—— 全靠你的程序 P。 只要你承认 P 存在，就无法逃脱这陷阱； 自己的假设让你遇寒冰。 争论的终点在何方？ 就算我不说，你也知道会怎样。 一个反证就说明：这个判断循环的程序 P 它的存在不可能。 你永远无法找到一台通用机， 让它判断任意程序是否会停机； 电脑无法成此事。所以用户 还需自己来捉虫。电脑终究还是输！ SCOOPING THE LOOP SNOOPER A proof that the Halting Problem is undecidable Geoffrey K. Pullum No general procedure for bug checks will do. Now, I won’t just assert that, I’ll prove it to you. I will prove that although you might work till you drop, you cannot tell if computation will stop. For imagine we have a procedure called P that for specified input permits you to see whether specified source code, with all of its faults, defines a routine that eventually halts. You feed in your program, with suitable data, and P gets to work, and a little while later (in finite compute time) correctly infers whether infinite looping behavior occurs. If there will be no looping, then P prints out ‘Good.’ That means work on this input will halt, as it should. But if it detects an unstoppable loop, then P reports ‘Bad!’ — which means you’re in the soup. Well, the truth is that P cannot possibly be, because if you wrote it and gave it to me, I could use it to set up a logical bind that would shatter your reason and scramble your mind. Here’s the trick that I’ll use — and it’s simple to do. I’ll define a procedure, which I will call Q, that will use P’s predictions of halting success to stir up a terrible logical mess. For a specified program, say A, one supplies, the first step of this program called Q I devise is to find out from P what’s the right thing to say of the looping behavior of A run on A. If P’s answer is ‘Bad!’, Q will suddenly stop. But otherwise, Q will go back to the top, and start off again, looping endlessly back, till the universe dies and turns frozen and black. And this program called Q wouldn’t stay on the shelf; I would ask it to forecast its run on itself. When it reads its own source code, just what will it do? What’s the looping behavior of Q run on Q? If P warns of infinite loops, Q will quit; yet P is supposed to speak truly of it! And if Q’s going to quit, then P should say ‘Good.’ Which makes Q start to loop! (P denied that it would.) No matter how P might perform, Q will scoop it: Q uses P’s output to make P look stupid. Whatever P says, it cannot predict Q: P is right when it’s wrong, and is false when it’s true! I’ve created a paradox, neat as can be — and simply by using your putative P. When you posited P you stepped into a snare; Your assumption has led you right into my lair. So where can this argument possibly go? I don’t have to tell you; I’m sure you must know. A reductio: There cannot possibly be a procedure that acts like the mythical P. You can never find general mechanical means for predicting the acts of computing machines; it’s something that cannot be done. So we users must find our own bugs. Our computers are losers! 这首不拘一格的小诗，正是图灵论证的点睛之笔。下面是这一论证思路的示意图。菱形代表循环检测程序 P，用来判断程序 Q（如流程图所示）是否会停机。 “这个程序将在它无限循环时停机，又将在程序会停机的情况下陷入循环！”Image Credit for serpent (right): Andrei 就像这条吃掉了自己尾巴的蛇一样，图灵通过自我指涉巧妙地展示了矛盾的存在。程序将在停机的情况下无限循环，又将在陷入循环的时候停机！为了解决这样的矛盾，我们就只能得出结论：这样的循环检测程序根本不可能存在。 这个的论证思路还产生了更加深远的影响。还有数不胜数的问题是计算机无法给出可信答案的，其中那些计算机程序无法实现的功能都是循环检测程序的变体，例如如何完美地识别出一个程序是否是病毒，或者是检查程序是否具有易被攻击的代码漏洞并完成修复。所以我们期待的万能杀毒软件，或者没有漏洞无懈可击的软件，都是不会出现的。另外，让一台计算机去判断两个程序是否能实现同样的功能也是不可行的，这对于那些必须要批改计算机课程中编程作业的可怜助教来说，实在是一个不幸的事实。 神奇的循环检测软件被图灵宣判了死刑，这说明计算机是存在一些功能上的限制的。每个人都有其约束，现在我们知道那些我们创造出来的“大脑”也有其限制，不失为一件让人感到安慰的事。 原文链接：https://www./2014/02/halting-problem/ |
|
|
