停機問題（halting problem）

假設你寫了一個工具，它能讀入任何程式加上其輸入，並在「完全不執行」的情況下告訴你：這個程式最終會結束，還是會卡在無窮迴圈裡。這樣的工具簡直是夢想：再也沒有當掉的 App、沒有掛住的伺服器。停機問題問的就是這樣的工具能不能存在。寫成是非題：給定一台機器 M 的描述與一個輸入 w，M 在 w 上會停機（結束）嗎？令人震驚的答案——由 Alan Turing 在 1936 年證明——是：沒有任何演算法能對每一組可能的 (M, w) 都正確回答這個問題。這個問題是不可判定的。

我們要小心釐清它說了什麼、沒說什麼。對某些程式判斷停機很容易：沒有迴圈的程式一定停機，唯一一行是 while(true) {} 的程式顯然永不停機。這個論斷講的是「一個通用演算法」必須對「所有」機器—輸入對都正確。我們可以把每一組這樣的對打包成字串，得到語言 HALT =（(M, w) 的編碼：機器 M 在輸入 w 上會停機）。問停機問題就是問 HALT 是否可判定，也就是是否有某台圖靈機總會停下並正確回答給定的 (M, w) 是否在 HALT 中。Turing 證明了這樣的判定器並不存在。

這不是「慢」或「難」的陳述。停機問題不只是解起來很貴，而是在一般情形下被證明無法解決，無論給你多少時間、記憶體或聰明才智都一樣。一個想當停機檢查器的程式有時可以拒絕回答（說「我不知道」），也可以對簡單情形快速作答，但它永遠無法成為一個全函數、永遠正確的判定器。這個單一結果是整個可計算性理論的門戶：一旦你接受「有一個精確的問題沒有演算法」，一整族關於程式的自然問題就隨之倒下。