的停止的问题是可计算性理论中的一个决策问题。它问，给定一个计算机程序和一个输入，这个程序会终止还是永远运行?例如，考虑以下Python程序:

1 2 3

x＝输入（）而x：通过

它读取输入，如果输入不为空，程序将一直循环。因此，如果输入为空，则程序将终止，这个特定问题的答案是“是，这个空输入上的程序将终止”，如果输入不为空，则程序将一直循环，而答案是“否，这个输入上的程序将不会终止”。

停顿问题可能是已被证实的最著名的问题不可判定的；也就是说，没有一个程序能够解决足够通用的计算机程序的停止问题。具体说明我们所讨论的计算机程序的类型是很重要的。在上面的例子中，它是一个Python程序，但在计算理论中，人们经常使用图灵机它被证明和“普通计算机”一样强大。1936年，艾伦·图灵用图灵机证明了图灵机的停止问题是无法确定的;也就是说，没有图灵机能够正确地决定(终止并产生正确的答案)所有可能的程序/输入对。

的决策问题 $H$，对于停顿问题，是所有的集合 $\{\lang p, x\ rangle | \text{程序\$p\$停止输入\$x\$}\}$，以获取“程序”(通常为“图灵机”)的适当定义，以及其中 $\ langle \ cdot \捕杀$表示某种编码。一个图灵机 $一个$解决了 $H$如果，给定任何输入 $\角p, x \角$，则终止于接受状态 $\lang p, x \rangle \in H$，否则终止于拒绝状态。请注意，这并不重要 $p$终止是因为它接受，或者拒绝，或者因为它得到某种错误;只要它终止并且不是永远循环， $一个$应该接受它。

反证法

假设存在图灵机 $一个$决定 $H$．现在考虑图灵机 $B$定义如下:它接受一个输入 $\ langle p \捕杀$,运行 $一个$在输入 $\lang p， \lang p \rangle \rangle$，当且仅当时停止 $一个$拒绝。也就是说, $B$需要一个程序 $p$运行所谓的图灵机，决定输入“程序”上的停止问题 $p$、输入 $\ langle p \捕杀$”;根据结果，如果它说"是" $p$在输入 $\ langle p \捕杀$“暂停”，然后它会一直循环下去，否则如果它说“不， $p$在输入 $\ langle p \捕杀$不停止”，那么它就终止了。请注意, $\ langle p \捕杀$是程序的编码吗 $p$转换为合适的输入(位串或自然数)，从而可被另一个程序接受为输入。

考虑一下当 $B$接收 $\ \捕杀langle B$作为输入。它运行 $一个$在输入 $\lang B， \lang B \rangle \rangle$．我们现在有两种情况:

• $一个$接受。这意味着 $B$在输入 $\ \捕杀langle B$暂停。但是根据定义 $B$,如果 $一个$接受我们将进入一个无限循环，如此 $B$在输入 $\ \捕杀langle B$毕竟没有停止。
• $一个$拒绝。这意味着 $B$在输入 $\ \捕杀langle B$不停止。但是根据定义 $B$,如果 $一个$拒绝我们将终止，等等 $B$在输入 $\ \捕杀langle B$暂停。

在这两种情况下，我们都得到了一个矛盾。这种矛盾的发生是因为我们假设存在 $一个$；它的存在让我们得以创造 $B$表现得不正确。因此 $一个$不可能存在，所以没有图灵机可以决定 $H$．

现实的例子^[1]

一种可视化的方法是想象手机上的应用程序。应用程序是图灵机的一种。有时应用程序崩溃是因为它们陷入了循环，没有停止。让我们假设一个聪明的团队发布了一个应用程序来检查这一点。这个应用程序，Checker应用程序可以解决停止的问题。

Checker应用程序检查一些应用程序 $米$．如果 $米$停止,然后 $检查器(M)$接受，这个应用程序将不会崩溃您的手机。如果 $米$循环,然后 $检查器(M)$拒绝，这个应用程序将崩溃你的手机。

假设一个邪恶的计算机科学家决定创建一个名为Paradox的应用程序。这个应用程序将有效地逆转Checker应用程序。因为Checker应用程序工作，这个也工作，它真的很简单:-它打开Checker应用程序，并输入自己到Checker应用程序。-如果Checker返回一个接受，那么Paradox应用程序强制手机循环和崩溃。-如果Checker应用程序返回拒绝，那么Paradox应用程序将停止，这意味着它不应该被拒绝，这是一个安全的应用程序，不会使你的手机崩溃。

有效地运行Paradox意味着运行Paradox(Checker(Paradox))。如果Paradox是一个糟糕的应用程序，会让你的手机崩溃，Checker会拒绝它，Paradox会返回暂停。Paradox(Checker(Paradox)) = Paradox(Checker(loop)) = Paradox(reject) = Halt如果Paradox是一款优秀的应用，那么它便会停止，然后Checker应用便会接受它，而Paradox便会崩溃你的手机。Paradox(Checker(Paradox)) = Paradox(Checker(halt)) = Paradox(accept) =循环因此，Checker应用程序说Paradox是好的，然后Paradox让你崩溃，或者Checker应用程序说Paradox是坏的，Paradox停止。这是一个矛盾。

现在有些人仍然不认为这是一种矛盾。对此我们要指出，这是一个超级任务，我们知道这在现实世界中是不可能的。一个超级任务是一个无限任务的不可计数的系列，例子包括汤普森的灯或芝诺悖论．我们知道运行Paradox实际上意味着Paradox(Checker(Paradox))这意味着Paradox(Checker(Paradox(Checker(Paradox)))))这意味着Paradox(Checker(Paradox(Checker(Paradox(Paradox(Checker))))))))等等。悖论软件要么让你的手机崩溃，要么不会。这是仅有的两种可能。但这一系列无限的检查在循环和停止之间来回切换，没有结果。

证明一个问题不可定的典型方法是用约简法。如果一个问题可以归结为停顿问题，那它就是不可确定的。

一个问题 $一个$是否可简化为问题 $B$如果解决方案 $B$可以用来解决吗 $一个$．如果 $一个$已经被证明是一个无法确定的问题，要证明是一个新的问题 $B$是不可确定的，那就足以说明一个解来了吗 $B$可以用来做决定吗 $一个$．这就产生了矛盾，因为它已经被证明了 $一个$是无法确定的，因此， $B$也不可判定的。

如果我们能解决忙碌的海狸问题，我们就能解决停顿的问题。

“忙碌的海狸”问题是确定一个问题的最大步数 $n$图灵机的状态之前停止．

如果我们有一个函数可以计算忙碌的海狸函数， $BB (n)$，我们就能知道任何图灵机在停止前的最大步数。这意味着我们可以知道我们要等多久机器才会停止，最终，我们会知道机器是否将停止。换句话说，如果我们有办法计算Busy Beaver函数，我们就可以用它来解决停顿问题。由于暂停问题是不可计算的，因此Busy Beaver函数是不可计算的。

如果可以解决停顿问题，就可以解决许多其他问题:

• 哥德巴赫猜想的可以决定。构造一个图灵机很容易，它可以测试每一个大于2的偶数自然数是否是两个质数的和;如果遇到任何反例，它会立即停止并报告找到了反例，否则它将永远运行。如果中止问题是可决定的，我们就可以决定这个程序是否会停止，从而给出哥德巴赫猜想的答案。
• Kolmogorov复杂度是可计算的。
• 忙碌的海狸函数也是可计算的。

了解那些无法确定的问题是很有用的，因为它有助于我们理解计算模型的局限性。

重要的是要注意，停止问题取决于我们正在考虑的程序。图灵机的停止问题是无法确定的。相反，有限状态自动机上的停止问题很容易确定;所有有限状态自动机停止。因此，指定模型非常重要。

普通计算机的停止问题也是可以确定的。要了解这一点，请注意内存中有有限数量的位，因此计算机可以处于有限数量的可能配置中。如果一个程序曾经重复一个配置，它将永远不会终止。因此，具有无限内存的图灵机可以模拟程序。根据鸽子洞原理，如果有的话 $N$程序可以在的配置中，但是我们已经对程序进行了模拟 $N + 1$步骤中，我们必须访问配置两次，因此程序永远不会终止。因此，普通计算机的停机问题也可以用图灵机来解决。

1. Husfeldt, T。The-Freeze-App-Does-Not-Exist．检索自2016年4月24日https://thorehusfeldt.net/2012/06/25/the-freeze-app-does-not-exist/