停顿问题

没有这样的程序（算法）可以计算是否有任何程序（算法）在给定的输入处结束（停止）.

那么，如何证明这个停机问题呢？

反驳！假设我们有一天制定了一种非常聪明的通用算法（我们称它为God_algo），您只需要给它一个程序（二进制描述），然后将其输入该程序的输入，它可以告诉您是否程序将在此输入上结束（停止），让我们编写算法:

bool God_algo（char *程序，char *输入）

{

如果（<程序>在<输入>上暂停）

返回true;

返回假；

}

在这里，我们假设，如果if的判断语句是您天才思维的结晶，那么它可以看到所有程序（如上帝）的命运. 现在，我们从God_algo派生出一种新算法:

布尔Satan_algo（char *程序）

{

如果（God_algo（程序，程序））

{

同时（1）; //永远循环！

返回假； //永远无法到达这里！

}

其他

返回true;

}

顾名思义，该算法是万恶之源. 当我们将此算法应用于自身时会发生什么？

Satan_algo（Satan_algo）;

让我们分析一下这个简单的呼叫:

很明显，对Satan_algo（Satan_algo）的调用要么能够返回到运行结束（停机），要么无法返回（永远循环）.

如果可以结束，则将建立Santa_algo算法中的if判断（因为God_algo（Santa_algo，Santa_algo）将返回true），因此程序将在（1）时进入包含无限循环的if分支； ，因此此Satan_algo（Satan_algo）调用将永远不会返回（结束）.

如果无法结束（停机），则if判断将失败，因此选择另一个if分支并返回true，即Satan_algo（Satan_algo）可以返回（停机）.

简而言之图灵停机问题 意义，我们有:

可以关闭Satan_algo（Satan_algo）=>无法关闭

Satan_algo（Satan_algo）无法停止=>可以停止

所以这既不是停下来也不是停下来图灵停机问题 意义，矛盾的.

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-177471-1.html