图灵机停机问题
我正在寻找图灵机停机问题的简单解释。我对这个话题很陌生，但我知道TMs是如何工作的基础，他们是如何枚举事物，机器配置等的，但我没有很好地处理暂停问题。图灵机停机问题
有人可以提供一个很好的解释这个话题吗？
让我们忽略图灵机的世界，只考虑计算机程序。这会使我们的推理不那么严格，但可能更容易遵循。
考虑以下任务：编写一个程序，给定程序P和该程序的输入，确定在给定该输入时程序是否终止。 （为了简单起见，我们假定程序不要求用户输入，也不涉及随机性，因此在同一输入上运行相同的程序总是会执行相同的操作）。是否有可能编写符合此描述的程序？答案是不。为了表明这一点，我们将使用一个证明，通过与相抵触。我们会假设，某人设法编写程序，然后证明如果发生这种情况，会发生一些可怕的事情。
想象一下，有人写一个函数，看起来像这样：
function willHalt(program, input)
该功能具有以下特性：
- 它总是返回一个值。
- 如果该函数返回true，那么在指定的输入上运行时，指定的程序最终会终止（暂停）。
- 如果该函数返回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编码。真的，数学背后的核心思想就是上面所展示的。
如果您有兴趣，对于我去年教过的班级，我将a guide to self-reference and undecidability放在一起，这可能会让您更深入地了解这种说法的方式。
暂停问题要求我们确定给定输入的程序是否会停止（达到最终状态）。图灵证明，没有任何算法可以确定任何给定的程序和输入。
算法可能花费任意长的时间来处理程序及其输入，但是对于所有程序和所有输入，该算法无法准确确定程序是否最终会停止。随着国家的每次变化，下一次都可能是最后一次。
暂停问题是decision problem的早期示例。
因为没有算法可以准确地回答'是的，它会停止'或'不，它不会暂停'停止问题，它不可能。
写得很好，医生... –
享受了很多读这个 – Petaflop