这个证明,停止问题是不可判定的,如何工作？

Question

我正在通过Sipser 对计算理论介绍中的停止问题进行证明,我主要关注的是下面的证据:

如果TM M不知道它何时循环(它不能接受或拒绝这就是为什么TM对所有字符串都是图灵可识别的),那么决策者H怎么能决定M是否可能在循环中？当TM D进行处理时,同样的问题将继续存在.

Answer 1

在阅读本文并尝试可视化证明之后,我想出了这段代码,这是对相关问题的答案中的代码的简化版本:

function halts(func) {
  // Insert code here that returns "true" if "func" halts and "false" otherwise.
}

function deceiver() {
  if(halts(deceiver))
    while(true) { }
}

如果halts(deceiver)返回true,deceiver将永远运行,如果它返回false,deceiver将停止,这与定义相矛盾halts.因此,这个功能halts是不可能的.

Answer 2

这是一个"矛盾的证据",这是一种荒谬的减少.(拉丁短语在理论课上总是很好......当然,只要它们有意义.)

该程序H只是一个带有两个输入的程序:表示某个机器的程序的字符串和输入.对于证据的目的,您只需承担程序H是正确的:它只是将停止接受如果M与接受w ^.你不需要考虑它会如何做到这一点; 事实上,我们即将证明它不能,没有这样的程序H可以存在,......

因为

如果这样的程序存在,我们可以立即建立另一个程序H"是^ h不能决定.但是,根据这个假设,没有这样的程序:H可以决定一切.因此,我们不得不得出结论,没有定义为我们定义H的程序是可能的.

顺便说一下,减少验证方法比你想象的更具争议性,考虑它的使用频率,特别是在计算机科学中.发现它有点奇怪,你不应该感到尴尬.这个神奇的术语是"非建设性的",如果你真的有野心,请向你的一位教授询问Errett Bishop对非建设性数学的批评.