停机问题

维基百科,自由的百科全书
跳转至: 导航搜索

停机问题(halting problem)逻辑数学可计算性理论的一个问题。通俗的说,停机问题就是判断任意一个程序是否会在有限的时间之内结束运行的问题。该问题等价于如下的判定问题:给定一个程序P和输入w, 程序P在输入w下是否能够最终停止。

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

用数学语言描述,则其本质问题为: 给定一个图灵机 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函数有两种返回值,死循环(1) 或 停机(0)
int K(P)
{
    if (H(P,P) == 1){
        return 0; // 如果H死循环,这里会停机
    }else{
        while(1){} // 这里会死循环
    }
}

现在假设求K(K),则若H(K, K)输出停机,K(K)死循环,但由定义知二者矛盾(这里与过程H的定义相矛盾,因为H(K, K)正是过程K(K)的结果。)。反之,H(K, K)输出死循环,则K(K)停机,两者一样矛盾。

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

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

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

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

参见[编辑]

参考文献[编辑]

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