停機問題

[編輯首段]維基百科，自由的百科全書

跳轉到: 導航, 搜索

停機問題（halting problem）是目前邏輯數學的焦點，和第三次數學危機的解決方案。其本質問題是: 給定一個圖靈機 T，和一個任意語言集合 S, 是否 T 會最終停機於每一個。其意義相同於可確定語言。顯然任意有限 S 是可判定性的，可數的(countable) S 也是可停機的，在使用 oracle 輸入的幫助下。

通俗的說，停機問題就是判斷任意一個程序是否會在有限的時間之內結束運行的問題。如果這個問題可以在有限的時間之內解決，可以有一個程序判斷其本身是否會停機並做出相反的行為。這時候顯然不管停機問題的結果是什麽都不會符合要求。所以這是一個不可解的問題。

停機問題本質是一階邏輯的不自恰性和不完備性。類似的命題有理發師悖論、全能悖論等。！

[編輯] 證明

設停機問題有解，即：存在過程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)的輸出相反的動作。

現在假設求K(K)，則若H(K, K)輸出停機，K(K)死循環，但由定義知二者矛盾。反之，H(K, K)輸出死循環，則K(K)停機，兩者一樣矛盾。

因此，H不是總能給出正確答案，故而不存在解決停機問題的方法。^[1]