停機問題

停機問題（英語：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不是總能給出正確答案，故前述的假設不成立，不存在解決停機問題的方法。^[1]

相似的悖論

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

停機測試悖論：計算機裡面有個測試程序，這個測試程序的原則是，當有程序不遞歸調用自己（輸出停機），測試程序就調用它（對應不停機）。如果程序遞歸調用自己（對應不停機），測試程序就不調用它（對應停機）。無法回答的問題是，測試程序遞歸調用自己嗎？

參見

參考文獻

[1]
pp. 179-180，《離散數學及其應用》，Kenneth H. Rosen著，機械工業出版社

外部連結

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

[1] [1]
pp. 179-180，《離散數學及其應用》，Kenneth H. Rosen著，機械工業出版社

[1]