停机问题

停机问题（halting problem）是目前逻辑数学的焦点，和第三次数学危机的解决方案。其本质问题是: 给定一个图灵机 T，和一个任意语言集合 S, 是否 T 会最终停机于每一个$s \in S$。其意义相同于可确定语言。显然任意有限 S 是可判定性的，可数的(countable) S 也是可停机的。

通俗的说，停机问题就是判断任意一个程序是否会在有限的时间之内结束运行的问题。如果这个问题可以在有限的时间之内解决，可以有一个程序判断其本身是否会停机并做出相反的行为。这时候显然不管停机问题的结果是什么都不会符合要求。所以这是一个不可解的问题。

停机问题本质是一阶逻辑的不自洽性和不完备性。类似的命题有理发师悖论、全能悖论等。

证明

设停机问题有解，即：存在过程H(P, I)可以给出程序P在输入I的情况下是否可停机。假设若P在输入I时可停机，H输出“停机”，反之输出“死循环”，即可导出矛盾：

显然，程序本身可以被视作数据，因此它可以被作为输入，故H应该可以判定当将P作为P的输入时，P是否会停机。所以我们设过程K(P)的流程如下：首先，它调用H(P, P)，如果H(P, P)输出“死循环”，则K(P)停机，反之K(P)死循环。即K(P)做与H(P, P)的输出相反的动作。

伪代码表示如下

int H(procedure,Input); // 这里的H函数有两种返回值，死循环 或 停机
int K(P)
{
    if (H(P,P) == 死循环){
        return  停机;
    }else{
        while(1){} // 这里会死循环
    }
}

现在假设求K(K)，则若H(K, K)输出停机，K(K)死循环，但由定义知二者矛盾。反之，H(K, K)输出死循环，则K(K)停机，两者一样矛盾。

因此，H不是总能给出正确答案，故而不存在解决停机问题的方法。

另外还有两个本质上相似的悖论：

理发师悖论：村子里有个理发师，这个理发师有条原则是，对于村里所有人，当且仅当这个人不自己理发，理发师就给这个人理发。如果这个人自己理发，理发师就不给这个人理发。无法回答的问题是，理发师给自己理发么？

停机测试悖论：计算机里有个测试程序，这个测试程序的原则是，对于计算机里所有程序，当且仅当这个程序不递归调用自己(输出停机)，测试程序就调用它(对应不停机)。如果这个程序递归调用自己（对应不停机），测试程序就不调用它（对应停机）。无法回答的问题是，测试程序递归调用自己么？

参见

• 理发师悖论
• 哥德尔不完备定理
• 未解決的數學問題