海之美文新闻资讯
停机问题
停机问题是目前逻辑学的焦点，也是第三次数学危机的解决方案。其本质问题是: 给定一个图灵机 T，和一个任意语言集合 S, 是否 T 会最终停机于每一个s∈S。其意义相同于可确定语言。显然任意有限 S 是可判定性的，可列的(countable) S 也是可停机的。
基本介绍
- 中文名：停机问题
- 外文名：halting problem
- 所属：逻辑学
- 实质：是一阶逻辑的不自洽性和不完备性
- 类似命题：理髮师悖论、全能悖论
- 套用学科：逻辑数学
概念
停机问题（英语：halting problem）是逻辑数学中可计算性理论的一个问题。通俗地说，停机问题就是判断任意一个程式是否能在有限的时间之内结束运行的问题。该问题等价于如下的判定问题：是否存在一个程式P，对于任意输入的程式w，能够判断w会在有限时间内结束或者死循环。
通俗的说，停机问题就是判断任意一个程式是否会在有限的时间之内结束运行的问题。如果这个问题可以在有限的时间之内解决，则有一个程式判断其本身是否会停机并做出相反的行为，这时候显然不管停机问题的结果是什幺都不会符合要求。所以这是一个不可解的问题。
停机问题本质是一高阶逻辑的不自恰性和不完备性。类似的命题有理髮师悖论、全能悖论等。
证明
假设停机问题有解，即：存在过程H(P, I)可以判断对于程式P在输入I的情况下是否可停机。假设P在输入I时可停机，H输出“停机”，反之输出“死循环”，即可导出矛盾：
显然，程式本身也是一种数据，因此它可以作为输入（例如Pascal的编译器本身就可以用Pascal所写成，所以程式在自己身上运行自己也是合理的），故H应该可以判定当将P作为P的输入时，P是否会停机。然后我们定义一个过程U(P)，其流程如下：
- U(P)调用H(P, P)：
* 如果H(P, P)进入死循环，U(P)就停机。
* 如果H(P, P)停机，U(P)就进入死循环。
* 也就是说，U(P)做的事情就是做出与H(P, P)的输出相反的动作。
伪代码及其注释表示如下：
int H(procedure,Input); // 这里的H函式有两种返回值，死循环(1) 或 停机(0)
int U(P)
{
if (H(P,P) == 1){ // 如果H死循环
return 0; // 此时会停机
}
else{ // 否则
while(1){} // 此时会死循环
}
}
上面把H(P, P)包装在U(P)内，也就是用U()来模拟H()。H()的输出可能出现两种状况：
- 假设H(U, U)输出停机 -> U(U)进入死循环：由定义知二者矛盾（与过程H的定义相矛盾，因为照H自己本来的定义，H(U, U)的结果应该和U(U)相同，但U()的定义却是永远输出与H()相反的结果。）
- 假设H(U, U)输出死循环 -> U(U)停机：两者一样矛盾。
因此，H不是总能给出正确答案，故前述的假设不成立，不存在解决停机问题的方法。
相似的悖论
理髮师悖论：村子里有个理髮师，这个理髮师有条原则是，对于村里所有人，若且唯若这个人不自己理髮，理髮师就给这个人理髮。如果这个人自己理髮，理髮师就不给这个人理髮。无法回答的问题是，理髮师给自己理髮幺？
停机测试悖论：计算机里有个测试程式，这个测试程式的原则是，对于计算机里所有程式，若且唯若这个程式不递归调用自己（输出停机），测试程式就调用它（对应不停机）。如果这个程式递归调用自己（对应不停机），测试程式就不调用它（对应停机）。无法回答的问题是，测试程式递归调用自己幺？
参见
- 理髮师悖论
- 哥德尔不完备定理
- 未解决的数学问题