停機問題

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

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

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

假設停機問題有解，即：存在過程H(P, I)可以判斷對於程序P在輸入I的情況下是否可停機。假設P在輸入I時可停機，H輸出“停機”，反之輸出“死循環”，即可導出矛盾：

顯然，程序本身也是一種數據，因此它可以作為輸入（例如Pascal的編譯器本身就可以用Pascal所寫成，所以程序在自己身上運行自己也是合理的），故H應該可以判定當將P作為P的輸入時，P是否會停機。然後我們定義一個過程U(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){} // 此時會死循環

}

}

上面把H(P, P)包裝在U(P)內，也就是用U()來模擬H()。H()的輸出可能出現兩種狀況：

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

理髮師悖論：村子裏有個理髮師，這個理髮師有條原則是，對於村裏所有人，當且僅當這個人不自己理髮，理髮師就給這個人理髮。如果這個人自己理髮，理髮師就不給這個人理髮。無法回答的問題是，理髮師給自己理髮麼？

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