停机时间问题|百度图书馆

关机问题的证明: 关机问题与NP型问题不同. NP型问题只是不知道它们是否有一个由多项式限制的算法，但是关闭问题已被证明是无法解决的. 停机问题是逻辑问题中的可计算性理论之一. 用外行的话来说，停机时间的问题是判断任何程序是否会在有限的时间内结束的问题. 如果可以在有限的时间内解决此问题，则可以使用一个程序来确定它是否将停止. 但是，在程序停止之前，无法确定它是否将停止. 因此，这是一个无法解决的问题. 艾伦·图灵（Alan Turing）在1936年证明，不存在能够解决停机问题的通用算法. 该证明的主要部分是计算机和程序的数学定义，即所谓的图灵机. 停机问题在图灵机上是无法确定的问题. 这是提出的第一个决定性问题之一. 用数学语言描述的基本问题是: 给定图灵机T和任意语言集S，T是否最终将在每个位置停止. 含义与可确定的语言相同. 显然，任何有限的S都是可确定的，可计数的S也是可停机的. 停机问题本质上是一阶逻辑的不一致性和不完整性. 类似的主张包括理发师悖论和全面悖论. 等待中. 假设可以确定关闭问题，则有一个判断程序P，可以判断是否有任何程序f停止了输入x的计算. 当针对x的f的计算停止时，P（f，x）= true. 当f不会停止x的计算时，P（f，x）= false. 定义一个新程序P1 P1（f，x）= while（P（f，x））;当f == P1时（由于P可以判断是否停止了任何程序，因此您也可以判断P1）P1（f，x）= P（f，x）当f！ = P1，我们现在讨论是否对任何输入x停止P1: 1.如果P1停止，则根据P1的定义图灵停机问题 意义，P（P1，x）== true P1（P1，x）= while（P（P1， X））;显然，P1不会停止，因此会产生矛盾. 2.如果P1没有停止，则根据P1的定义图灵停机问题 意义，P（P1，x）==假. P1（P1，x）= while（P（P1，x））;显然，P1将会停止并且也会产生矛盾. 结论: 不存在可以对任何输入进行判断的程序. 也就是说，“停机时间的问题是无法解决的. ”

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