基本介紹
概念,證明,相似的悖論,參見,
概念
停機問題（英語：halting problem）是邏輯數學中可計算性理論的一個問題。通俗地說，停機問題就是判斷任意一個程式是否能在有限的時間之內結束運行的問題。該問題等價於如下的判定問題：是否存在一個程式P，對於任意輸入的程式w，能夠判斷w會在有限時間內結束或者死循環。
通俗的說，停機問題就是判斷任意一個程式是否會在有限的時間之內結束運行的問題。如果這個問題可以在有限的時間之內解決，則有一個程式判斷其本身是否會停機並做出相反的行為，這時候顯然不管停機問題的結果是什麼都不會符合要求。所以這是一個不可解的問題。
證明
假設停機問題有解，即：存在過程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){} // 此時會死循環
}
}
上面把H(P, P)包裝在U(P)內，也就是用U()來模擬H()。H()的輸出可能出現兩種狀況：
- 假設H(U, U)輸出停機 -> U(U)進入死循環：由定義知二者矛盾（與過程H的定義相矛盾，因為照H自己本來的定義，H(U, U)的結果應該和U(U)相同，但U()的定義卻是永遠輸出與H()相反的結果。）
- 假設H(U, U)輸出死循環 -> U(U)停機：兩者一樣矛盾。
因此，H不是總能給出正確答案，故前述的假設不成立，不存在解決停機問題的方法。
