4

我正在寻找图灵机停止问题的简单解释。我知道 TM 的工作原理、它们如何枚举事物、机器配置等，但我无法很好地处理停机问题。

有人可以很好地解释这个话题吗？

4

2 回答 2

7

让我们暂时忽略图灵机的世界，只考虑计算机程序。这将使我们的推理不那么严格，但可能更容易理解。

考虑以下任务：编写一个程序，给定程序 P 和该程序的输入，确定在给定该输入时程序是否会终止。（为简单起见，我们假设程序不要求用户输入并且不涉及随机性，因此在相同的输入上运行相同的程序总是做同样的事情）。是否可以编写符合此描述的程序？答案是不。为了证明这一点，我们将使用反证法。我们会假设，不知何故，有人设法编写了程序，然后表明如果是这种情况会发生可怕的事情。

想象一下，有人编写了一个如下所示的函数：

function willHalt(program, input)

此函数具有以下属性：

  1. 它总是返回一个值。
  2. 如果函数返回 true，则指定的程序在指定输入上运行时最终会终止（停止）。
  3. 如果函数返回 false，则指定程序在指定输入（循环）上运行时永远不会终止。

在这一点上，我们可以开始怀疑是谁编写了这个函数。

他们：“嘿！我刚刚写了一个程序，它可以接收任何程序和输入，它会告诉你程序是否在输入时停止！”

我们：“哦，真的吗？它可以接收任何程序？任何程序都可以吗？”

他们：“是啊！我就是这么说的。”

我们：“那么，这里的这个程序怎么样？”

然后我们给他们这个程序：

function trickyTricky(input) {
    /* Ask whether this program (named trickyTricky) is going to halt
     * on its input.
     */
    if (willHalt(trickyTricky, input)) {
        /* If so, loop infinitely! */
        while (true) { }
    } else {
        /* If not, do nothing and stop running! */
    }
}

所以让我们想想这个程序做了什么。

  • 首先，想象一下这个程序，当给定一个特定的输入时，最终在该输入上运行时终止。仔细跟踪程序，看看会发生什么。首先，它询问willHalt它是否会终止，答案是“是的，会的”。这意味着该if语句的计算结果为真......所以程序然后进入无限循环！糟糕——程序应该停止，但它却无限循环！

  • 其次，想象一下这个程序，当给定一个特定的输入时，进入一个无限循环。仔细跟踪程序，看看会发生什么。首先，它询问willHalt它是否会终止。答案是否定的，所以它不会进入if语句，而是立即完成运行。但这并不好 - 程序应该无限循环，但它却终止了！

所以现在我们有一个问题。如果您真的可以编写一个函数来告诉您程序是否会因某些输入而停止，那么您可以使用该程序来构建一个与它应该做的相反的程序——这是不可能的！

停止问题只是将上述想法形式化的数学上严格的方法。我们不讨论程序，而是讨论图灵机和 TM 编码。但是，实际上，数学背后的核心思想就是上面显示的内容。

如果你有兴趣，对于我去年教的一门课，我整理了一份关于自我参照和不可判定性的指南，可能会让你对这种论证方式的运作方式有更多的阐述。

于 2016-07-22T16:46:38.270 回答
1

停止问题要求我们确定给定输入的程序是否会停止（达到某个最终状态）。图灵证明了不存在可以为任何给定程序和输入确定这一点的算法。

算法可以花费任意长的时间来处理程序及其输入，但是对于所有程序和所有输入，算法永远无法准确地确定程序是否最终会停止。随着状态的每次变化，下一个可能是最后一个。

停止问题是决策问题的早期例子。

因为没有算法可以准确地回答“是，它会停止”或“不，它不会停止”对于停止问题，它是不可判定的。

于 2016-07-22T16:54:02.360 回答