第六百七十七章 停機問題（邏輯學）(第1/1頁)
章節報錯
圖靈一開始假設，有可能製造出一臺圖靈機，它可以計算出一個程式在給定某種輸入後是否會停止或永遠執行。然後他證明，這臺機器會導致一個矛盾，所以不可能存在。
圖靈提到的這個想法，後來被稱為停機問題。今天的軟體開發人員將其稱為無限迴圈，這是他們在編寫迴圈或遞迴函式時遇到的一個問題。
戴維斯在想什麼是可以計算的，只要把不可以計算的全部排除，剩下的就是全部可以計算的了。
停機問題就是判斷任意一個程式是否能在有限的時間之內結束執行的問題。
該問題等價於如下的判定問題：是否存在一個程式p，對於任意輸入的程式w，能夠判斷w會在有限時間內結束或者死迴圈。
最後戴維斯說：“存在一種圖靈機，其停機問題是遞迴無解的。”
停機問題就是判斷任意一個程式是否會在有限的時間之內結束執行的問題。如果這個問題可以在有限的時間之內解決，則有一個程式判斷其本身是否會停機並做出相反的行為，這時候顯然不管停機問題的結果是什麼都不會符合要求。所以這是一個不可解的問題。
停機問題本質是一高階邏輯的不自恰性和不完備性。類似的命題有理髮師悖論、全能悖論等。