图灵机停机问题的解释

Question

我正在寻找图灵机暂停问题的简单解释.我知道TM的工作原理,它们如何枚举,机器配置等等,但我没有很好地处理暂停问题.

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

Answer 1

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

考虑以下任务:编写一个程序,给定程序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语句的计算结果为true ...因此程序进入无限循环!糟糕 - 该程序应该停止,但它无限循环!

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

所以现在我们遇到了问题.如果你真的真的可以编写一个函数来告诉你程序是否会停止某些输入,那么你可以使用该程序来构建一个与它应该做的相反的程序 - 这是不可能的!

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

如果你感兴趣的是,对于我去年教过的一门课程,我整理了一本自我引用和不可判断性的指南,可能会让你对这种论证的作用方式有更多的阐述.