來源：互聯網
停機問題（halting problem）是目前邏輯學的焦點，和第三次數學危機的解決方案。
概念
停機問題（halting problem）是目前邏輯數學的焦點，和第三次數學危機的解決方案。其本質問題是: 給定一個圖靈機 T，和一個任意語言集合 S, 是否 T 會最終停機于每一個。其意義相同于可確定語言。顯然任意有限 S 是可判定性的，可數的(countable) S 也是可停機的，在使用 Oracle數據庫 輸入的幫助下。
通俗的說，停機問題就是判斷任意一個程序是否會在有限的時間之內結束運行的問題。如果這個問題可以在有限的時間之內解決，可以有一個程序判斷其本身是否會停機并做出相反的行為。這時候顯然不管停機問題的結果是什么都不會符合要求。所以這是一個不可解的問題。
停機問題本質是一階邏輯的不自恰性和不完備性。類似的命題有理發師悖論、全能悖論等。
證明
首先，判定一個程序是否會停機，是指：對于其的任意一個輸入，可判定其是否停機。那么假定這樣的圖靈機存在，設為H。其工作過程不妨設為：若對于任意一個程序M可停機則輸出1，反之輸出0（由于其是可判定的）。那么可以構造另一程序D，其工作過程為：以H輸出為輸入，若輸入為1則不停機，反之停機。
由于H可判定所有程序，那么其也可判定D，若其判定D輸入1時不停機，則其輸出0，而由于D的定義知它是可停機的，反之亦然。故停機問題無算法解。
參考資料 >