我正在寻找一个关于图灵机停止问题的简单解释。我知道TM如何工作的基础，它们如何枚举事物，机器配置等，但我对停止问题没有很好的处理能力。
有人能很好地解释这个话题吗？
让我们暂时忽略图灵机的世界，只考虑计算机程序。这将使我们的推理不那么严格，但可能更容易遵循。
考虑以下任务：编写一个程序，在给定程序p和该程序的输入的情况下，确定该程序在给定该输入时是否会终止。（为了简单起见，我们假设程序不要求用户输入，也不涉及随机性，所以在同一输入上运行同一程序总是做同样的事情）。是否可以编写符合此描述的程序？答案是否定的。为了证明这一点，我们将使用矛盾证明。我们会假设，不知何故，有人设法编写了这个程序，然后表明如果是这样的话，会发生可怕的事情。
想象一下，有人写了一个看起来像这样的函数：
function willHalt(program, input)
此函数具有以下属性：
- 它总是返回一个值
- 如果函数返回true，那么指定的程序在指定的输入上运行时最终会终止（暂停）
- 如果函数返回false，则指定的程序在指定的输入上运行时永远不会终止（循环）
在这一点上，我们可以开始怀疑谁写了这个函数。
他们："嘿！我刚刚写了一个程序，可以接收任何程序和输入，它会告诉你程序是否在该输入上停止！"
我们："哦，真的吗？它可以接收任何程序？任何程序？"
他们："是的！我就是这么说的。"
Us："那么，这个程序在这里怎么样？"
然后我们给他们这个程序：
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编码。实际上，数学背后的核心思想正是上面所展示的。
如果你感兴趣的话，在我去年教的一门课上，我整理了一本关于自我参考和不确定性的指南，这可能会让你对这种争论方式的运作方式有更多的了解。
停止问题要求我们确定给定输入的程序是否会停止（达到某种最终状态）。图灵证明，对于任何给定的程序和输入，都不存在能够确定这一点的算法。
算法可以花费任意长的时间来处理程序及其输入，但对于所有程序和所有输入，算法永远无法准确地确定程序最终是否会停止。随着状态的每一次变化，下一次可能是最后一次。
停顿问题是决策问题的早期例子。
由于不存在能够准确回答"是，它将停止"或"否，它不会停止"的算法来解决停止问题，因此是不可确定的。