“判定问题”（德语entscheidungsproblem，英语decision problem）是可计算性理论的核心问题，由希尔伯特于1900年在巴黎第二届国际数学家大会上提出：是否存在这样一种确定的方法，在理论上可适用于任何假设，并且能够保证对无论是否正确的假设都能给出一个正确的结果？（https://zh.wikipedia.org/wiki/決定性問題）。图灵于1936年在他那篇著名的论文“论可计算数及其在判定问题上的应用”中给予了否定的回答。

人们一般将此“判定问题”表述为“停机问题”：是否存在一个图灵机能判断任一图灵机停机？首先假设存在一个能够判断任一图灵机停机的图灵机，然后利用康托尔的对角线法构造出一个类似于“我在撒谎”的悖论，于是通过反证法证明了不存在这样的万能图灵机，即“停机问题”是不可判断的，从而给出了希尔伯特的“判定问题”的否定回答。

然而，“停机问题”的本质经常未得到人们的正确认识，比如维基网（https://zh.wikipedia.org/wiki/停机问题）将“停机问题”理解成：

通俗地说，停机问题就是判断任意一个程序是否会在有限的时间之内结束运行的问题。该问题等价于如下的判定问题：给定一个程序P和输入w，程序P在输入w下是否能够最终停止。

实质上，“判断任一图灵机（程序）停机（停止）”与“判断是否存在一个图灵机能判断任一图灵机停机”，是二个层次完全不同的问题，前者是暗中肯定了有一台图灵机用以判断别的机器是否能停机，这是“真、假”判断；后者是质疑是否存在这样一台判断机去判断所有机器能否停机；前者是“判断”，而后者是对“判断”的“判断”。“停机问题”的证明正是具体化了这二个不同的层次，然后又将它们同一化造成“自我否定”，以此来证明不存在一个能判断任一图灵机停机的图灵机。

正确理解“停机问题”关键在于，“停机问题不可判断”这个结论等同于逻辑上的悖论——不可说，这是由人做出的结论，不是直接由机器给出的答案。

“停机问题”揭示的是不存在一个能判断任一图灵机停机的图灵机，这与逻辑悖论相同，但这个问题并没有因此而被抹杀，“停机问题不可判断”只是表明：对停机问题不存在确定性的算法，这是对机器能力而言，但对人的能力而言，这个问题既不能肯定也不能否定，正是在此意义上，“停机问题”成为了“不确定性问题（Nondeterministic Problem，NP）”，与确定性的“可计算问题”有本质的区别。

但是我们还要指出，“停机”在这里的意义是得到确定性的结果，与图灵论文中的“可计算数”相同，但对于“无限循环小数”这样的“可计算数”来说，正是机器不“停机”才能计算这个循环小数：A sequence is said to be computable if it can be computed by a circle-free machine [1]（这个circle-free 可以指机器处在不停止、但没有进入“死循环”的计算过程中），我们在这个特定的机器状态意义上说，机器状态是可以表示“不确定性”的意义的，但这与以前博文中所论的NDTM（Nondeterministic Turing Machine）完全不同。指出这一点有助于对NP（Nondeterministic Problem）的深入理解。    

参考文献：

[1] A. M. Turing, On Computability Numbers, with an Application to the Entscheidungsproblem. https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf