我试图理解为什么不可能编写一个程序 H 来检查特定输入上的另一个程序 P 是否会停止（停止问题），但我无法清楚地了解它。
尽管直觉告诉我们，如果这个程序 H 试图运行一个不会停止的程序 P，那么 H 本身就会进入一个循环。但我不认为这是证明背后的想法。
任何人都可以用简单的外行术语解释证明吗？
问问题
122 次
2 回答
4
证明背后的想法是矛盾的。
假设有一个停止问题机器M可以解决停止问题，并且0如果某些输入程序无法完成，并且1如果它会完成，则产生。M保证完成。
创建一台新机器H。
使用（本身）的输入H运行，如果答案为 1 - 进入无限循环，否则 - 停止。MHM
现在，如果你M在 input 上运行会发生什么H？
如果答案是1- 那就错了，因为H运行M，并且将进入无限循环。
如果答案是0- 它也是错误的，因为H会停止。
因此，它与正确的假设相矛盾M——因此不存在这样的M.
直觉上——这就像说没有神谕这样的东西，因为如果“你”告诉我你是神谕，我问你——我要举起哪只手臂？
然后，我会等待你的回答——然后做相反的事情——这与预言机确实是预言机的说法相矛盾。
于 2015-04-19T09:48:11.253 回答
3
图灵为此使用了矛盾证明（又名简化为荒谬）：
这个想法是假设实际上有这样一台机器H，它给定任何程序p，输入i会告诉我们天气p停止。
鉴于H此，我们可以对其进行修改并创建一台新机器。
我们将在H' 输出之后添加另一部分，如果H输出是，我们的机器将无限循环，
如果H输出否，我们的新机器将停止。
我们将调用我们的新机器H+。
现在，当我们H+向自身（作为 programp和 input i）喂食时，就会出现悖论。
那是因为如果H+ 确实停止了，我们得到了一个肯定的答案（来自该H部分），但是它会永远循环。
但是，如果H+ 不停止，我们会得到一个没有回答（来自该H部分），但是它会停止。
这在这个电脑迷情节中得到了很好的解释。
于 2015-04-19T10:03:01.703 回答