【计算机理论基础】停机问题（Halting Problem）

1 停机问题的来源

        Alan Turing: 《On Computable Numbers, with an Application to the Entscheidungsproblem》 

        resource: https://people.math.ethz.ch/~halorenz/4students/Literatur/TuringFullText.pdf

        停机问题（Halting Problem）：是否存在一个算法可以判断任意的程序是否会在有限时间内停止执行，还是会陷入无限循环？

2 为什么提出停机问题

        上一篇文章中，我们讲到了图灵机（Turing Machine），为什么需要将停机问题呢？我的理解是，这篇文章是图灵为了回答判定问题，判定问题就是“是否存在一个通用的算法或者方法，能够判断任何一个数学命题是真还是假的”，有了这个背景，我们再进行下一步理解。

        如果想要说明这个问题，我们首先可以看能不能找到哪些命题是不可以被回答的。然后图灵提出了图灵机的概念，并总结“任何可以计算的问题或者过程都可以通过图灵机来表达”，图灵机提供了一个定义“计算”或“算法”的精确方法，它能解决的问题被称为可计算问题。然后通过停机问题证明了“并非所有问题都可以由图灵机在有限时间内解决”，也就是说“存在不可解的问题（或者说图灵机不可解的问题）”。那么就是说“没有一种通用的算法，能够判断一个程序和输入是否会在有限的时间内停下来”，那么就是说“没有一种通用的算法或方法，能够判断一个命题是真或假”，从而便回答了“判定问题”。

3 怎么证明停机问题不可解

        图灵通过一种对角线论证和归谬法来证明停机问题是不可解的。

        图灵假设有一个“判定器”可以决定任意图灵机是否会在给定输入下停机。为了证明这个问题不可解，图灵构造了一个特殊的图灵机 M，当这个机器接收到自身的描述作为输入时，会导致自我矛盾：

1. 假设：存在一个通用的算法 H(M,x)，该算法能够判定图灵机 M是否会在输入 x 上停机。

2. 构造新的机器 D：该机器使用 H 作为子程序，它接受一个图灵机描述 M 作为输入并做如下操作：

   • 如果 H(M,M)返回“停机”，则D不停机，进入无限循环。
   • 如果 H(M,M)返回“不停机”，则D停机。

3. 矛盾：现在将 D自己作为输入，即 D(D)。根据 H 的判定：

   • 如果 D(D) 停机，那么 H(D,D)必须返回“不停机”，但这与 D(D) 会停机相矛盾。
   • 如果 D(D) 不停机，那么 H(D,D)必须返回“停机”，但这与 ( D(D) 不停机相矛盾。

        因此，图灵得出结论，不可能存在这样的算法可以解决所有情况下的停机问题。这就是停机问题不可判定性的证明​。