停机问题

停机问题（英语：halting problem）是逻辑数学中可计算性理论的一个问题。通俗地说，停机问题就是判断任意一个程序是否能在有限的时间之内结束运行的问题。该问题等价于如下的判定问题：是否存在一个程序P，对于任意输入的程序w，能够判断w会在有限时间内结束或者死循环。

艾伦·图灵在1936年用对角论证法证明了，不存在解决停机问题的通用算法。这个证明的关键在于对计算机和程序的数学定义，这被称为图灵机。停机问题在图灵机上是不可判定问题。这是最早提出的决定性问题之一。

用数学语言描述，则其本质问题为: 给定一个图灵机T，和一个任意语言集合S，是否T会最终停机于每一个。其意义相同于可确定语言。显然任意有限 S 是可判定性的，可数的（countable）S 也是可停机的。

停机问题包含了自我指涉，本质是一阶逻辑的不完备性，类似的命题有理发师悖论、全能悖论等。

证明

假设停机问题有解，即：存在过程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函数有两种返回值，死循环(0) 或 停机(1)
int U(P)
{
    //H(P,P) == 0时则跳出循环，程序正常结束；H(P,P)==1时则进入死循环中。
    while(H(P,P)){}
    return 0;
}

接下来考虑U(U)的运行结果。H(U,U)的输出可能出现两种状况：

  • 假设H(U, U)输出“停机” -> U(U)进入死循环：由定义知二者矛盾（与过程H的定义相矛盾，因为照H自己本来的定义，H(U, U)的结果应该和U(U)相同，但U()的定义却是永远做出与H()相反的结果。）
  • 假设H(U, U)输出死循环 -> U(U)停机：两者一样矛盾。

因此，H不是总能给出正确答案，故前述的假设不成立，不存在解决停机问题的方法。[1]

相似的悖论

理发师悖论：村子里有个理发师，这个理发师有条原则是，只要村子里有人不自己刮胡子，理发师就给这个人刮胡子。如果这个人自己刮胡子，理发师就不给这个人刮胡子。无法回答的问题是，理发师会自己刮胡子吗？

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

参见

参考文献

  1. ^ pp. 179-180，《离散数学及其应用》，Kenneth H. Rosen著，机械工业出版社

外部链接