本页使用了标题或全文手工转换

停机问题

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

停机问题英语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){ // 如果H死循环
        return 0; // 此时会停机
    }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著,机械工业出版社

外部链接[编辑]