停机问题是什么？图灵证明了有些问题计算机永远无法解决

停机问题（Halting Problem）是计算机科学中最著名的“不可解”问题，由英国数学家艾伦·图灵（Alan Turing）在 1936 年提出。它出自图灵的著名论文《论可计算数及其在判定问题上的应用》，发表在《伦敦数学会会刊》上。在这篇论文中，图灵首次提出了图灵机的概念，为现代计算机科学奠定了理论基础。

问题是什么

停机问题问的是：能不能写出一个通用的程序，任意给它一个程序和这个程序的输入，它都能判断出：这个程序运行后，最终会停下来，还是会永远运行下去、陷入死循环？这看上去是一个很实用的需求：如果有这样一个检查器，就能自动发现软件中的死循环错误了。图灵的结论是：这样的通用程序不可能存在。

图灵是怎么证明的

证明用的是反证法，思路很巧妙。假设存在这样一个万能的检查程序，叫它 H：输入任何一个程序 P 和输入 x，H 都能正确回答“P 在 x 上会停”或“不会停”。

那么，我们可以利用 H 构造一个“捣蛋”程序 D：D 接收一个程序 P 作为输入，然后问 H“P 以它自己为输入时会不会停”。如果 H 说“会停”，D 就故意进入死循环；如果 H 说“不会停”，D 就立刻停下。

现在，把 D 自己作为输入交给 D 运行，会发生什么？如果 D 会停，那么按照 D 的规则，H 必须说了“不会停”，但 H 的判断是正确的，矛盾；如果 D 不会停，那么 H 必须说了“会停”，又矛盾。无论哪种情况都自相矛盾，所以最初的假设错了：万能的检查程序 H 不可能存在。这种“自我指涉”的论证方式，与哥德尔不完备定理的证明有异曲同工之妙。

意义

停机问题揭示了计算的根本极限：存在一些明确定义的问题，任何计算机、任何算法都无法解决，无论计算能力有多强。它与“判定问题”直接相关，回答了希尔伯特提出的是否存在一种机械方法判定所有数学命题真假的问题。它的推论影响深远：比如赖斯定理指出，判断程序的任何非平凡的行为性质都是不可判定的。这也是为什么现实中的程序分析工具只能做近似的检查，无法完美地找出所有错误。