停機問題

停機問題（英語：halting problem）是邏輯數學中可計算性理論的一個問題。通俗地說，停機問題就是判斷任意一個程式是否能在有限的時間之內結束執行的問題。該問題等價於如下的判定問題：是否存在一個程式P，對於任意輸入的程式w，能夠判斷w會在有限時間內結束或者無窮迴圈。

艾倫·圖靈在1936年用對角論證法證明了，不存在解決停機問題的通用演算法。這個證明的關鍵在於對電腦和程式的數學定義，這被稱為圖靈機。停機問題在圖靈機上是不可判定問題。這是最早提出的決定性問題之一。

用數學語言描述，則其本質問題為: 給定一個圖靈機T，和一個任意語言集合S，是否T會最終停機於每一個$s\in S$。其意義相同於可確定語言。顯然任意有限 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不是總能給出正確答案，故前述的假設不成立，不存在解決停機問題的方法。

相似的悖論

理髮師悖論：村子裡有個理髮師，這個理髮師有條原則是，只要村子裡有人不自己刮鬍子，理髮師就給這個人刮鬍子。如果這個人自己刮鬍子，理髮師就不給這個人刮鬍子。無法回答的問題是，理髮師會自己刮鬍子嗎？

停機測試悖論：電腦裡面有個測試程式，這個測試程式的原則是，當有程式不遞迴呼叫自己（輸出停機），測試程式就呼叫它（對應不停機）。如果程式遞迴呼叫自己（對應不停機），測試程式就不呼叫它（對應停機）。無法回答的問題是，測試程式遞迴呼叫自己嗎？

參見

• 柴廷常數
• 理髮師悖論
• 哥德爾不完備定理
• 未解決的數學問題

外部連結

• 顧森解釋停機問題 （頁面存檔備份，存於網際網路檔案館）和證明 （頁面存檔備份，存於網際網路檔案館）