druid169

2017-01-02 17:29 






　　

Image: Armin Cifuentes/Flickr

　　撰文AATISH BHATIA

　　编译张竞文 赵维杰

　　计算机可以驾驶汽车，可以控制火星探测器登陆，还可以在《危险边缘》智力问答节目里击败人类......但是，有没有什么事情是计算机永远都做不到的呢？

　　计算机当然会被它们的硬件所限制，比如我的智能手机，（暂时）并不能同时当电动剃须刀用。但是这些只是物理上的限制，如果我们一心想做，总是能够克服的。所以让我把问题描述得更准确一点：有没有什么计算机永远无法给出解答的问题？

　　当然了，现在有很多问题计算机都很难给出解答。例如，在学校，我们会学习因数分解（30 = 2 × 3 × 5, 42 = 2 × 3 × 7），小孩子们都知道要按照一个简单的程序去进行计算。但是对巨大数字进行因数分解并不容易，直到2007年，如果有人能对以下的数字进行因数分解，就能得到十万美元的奖金。这个数字是：

•135066410865995223349603216278805969938881475605667027524485143851526510604859533833940287150571909441798207282164471551373680419703964191743046496589274256239341020864383202110372958725762358509643110564073501508187510676594629205563685529475213500852879416377328533906109750544334999811150056977236890927563


　　不仅如此，直到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

　　就像这条吃掉了自己尾巴的蛇一样，图灵通过自我指涉巧妙地展示了矛盾的存在。程序将在停机的情况下无限循环，又将在陷入循环的时候停机！为了解决这样的矛盾，我们就只能得出结论：这样的循环检测程序根本不可能存在。

　　这个的论证思路还产生了更加深远的影响。还有数不胜数的问题是计算机无法给出可信答案的，其中那些计算机程序无法实现的功能都是循环检测程序的变体，例如如何完美地识别出一个程序是否是病毒，或者是检查程序是否具有易被攻击的代码漏洞并完成修复。所以我们期待的万能杀毒软件，或者没有漏洞无懈可击的软件，都是不会出现的。另外，让一台计算机去判断两个程序是否能实现同样的功能也是不可行的，这对于那些必须要批改计算机课程中编程作业的可怜助教来说，实在是一个不幸的事实。

　　神奇的循环检测软件被图灵宣判了死刑，这说明计算机是存在一些功能上的限制的。每个人都有其约束，现在我们知道那些我们创造出来的“大脑”也有其限制，不失为一件让人感到安慰的事。

本帖最近评分记录

• 寂寞的季节1 金币 +5 转帖分享，红包献上！ 2017-1-4 14:06