turing-machines - 图灵机停机问题的解释

Question

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

有人可以对这个主题提供一个很好的解释吗？

Answer 1

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

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

想象一下，有人写了一个看起来像这样的函数:

function willHalt(program, input)

该函数具有以下属性:

它总是返回一个值。

如果函数返回 true，则指定的程序在指定的输入上运行时最终会终止(停止)。

如果函数返回 false，则在指定的输入(循环)上运行时，指定的程序永远不会终止。

在这一点上，我们可以开始怀疑编写此函数的人。

Them: "Hey! I just wrote a program that can take in any program and and input, and it will tell you whether or not the program halts on that input!"

Us: "Oh really? It can take in any program? Any program at all?"

Them: "Yeah! That's what I said."

Us: "Well, then, what about this program right here?"

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

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 编码。不过，实际上，数学背后的核心思想就是上面显示的内容。

如果你有兴趣，我去年教的一门课，我整理了 a guide to self-reference and undecidability这可能会让你对这种论证风格的运作方式有更多的了解。