如何通俗地解释停机问题（Halting Problem）？ - 知乎

本文转载自：如何通俗地解释停机问题（Halting Problem）？ - 黄雁捷 Anton (opens new window)的回答 (opens new window) - 知乎

就我个人的理解来说，既然要通俗，肯定会不严谨。所以如果这个回答能够引起题主些许的兴趣与兴致，我还是非常推荐楼主去了解数学与编程~~毕竟这些东西还是要用数学语言说才准确详实

如果不要求太准确的话，我想停机问题大概可以这样子无数学语言地通俗解释：

======

考虑一个魔法王国

在这里魔法可以解锁、可以解梦、可以解方程、可以解路边萌妹子的衣服，总而言之，魔法可以解决很多问题

然后人们在想：有没有什么问题是过去、现在、甚至将来可能出现的任何魔法，都解决不了的呢？

答案是有的

一个大魔法师，就发现了一个魔法解决不了的问题——停机问题

所谓的停机问题，简单地说就是这个问题：有没有办法判断任意一个魔法是否是永久持续的

因为魔法有两种嘛，有的魔法是暂时性的（也就是“会停机的”，比如诸葛祭风术）；而有的魔法是永久持续的（比如点石成金术）

而大魔法师证明了：判断任意一个魔法是否是永久持续的——这个问题，是魔法解决不了的

那么，是怎么证明的呢？

首先，假设这个问题可以用魔法解决。那我们不妨把这个魔法叫做【邪王真眼术】 ：判断给出的任意魔法是否是永久持续的：如果是永久持续的，就睁开眼睛；如果不是，就闭上眼睛。

然后，因为邪王真眼术是对应任意魔法的，那么显然我们可以给定一个新的魔法——【SCP173术】：当这个魔法成为【邪王真言术】的目标后，如果眼睛闭上了，就控制一个雕像不停地乱跑；如果眼睛睁开了，就停止。

现在，以【SCP173术】为目标施放【邪王真眼术】，我们发现：

1. 如果后者做出了“不是永久持续”的判断，就会使前者不停地乱跑，成为“是永久持续”的魔法
2. 如果后着做出了“是永久持续”的判断，就会使前者停下，成为“不是永久持续”的魔法

无论怎样，都会有矛盾

在整个推理过程中，我们只做过唯一的假设。而现在结果推出了矛盾，因此唯一的可能就是那个假设是错的——

也就是说，这个问题不可以用魔法解决

======

看完以后，上文的“魔法”都换成“程序”来理解就差不多了

有兴趣的话，最好还是在了解大意的基础上，再对照严格的数学语言看一遍吧 ：)

编辑于 2014-01-30 02:42