停机问题

停机问题（英語：）是逻辑数学中可计算性理论的一个问题。通俗地说，停机问题就是判断任意一个程序是否能在有限的时间之内结束运行的问题。该问题等价于如下的判定问题：是否存在一个程序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函数有两种返回值，死循环(1) 或 停机(0)
int U(P)
{
    if (H(P,P) == 1){ // 如果H死循环
        return 0; // 此时会停机
    }else{ // 否則
        while(1){} // 此时会死循环，而這是個空迴圈
    }
}

接下来考虑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著，机械工业出版社

外部链接
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.