圖靈機停機問題(The Halting Problem)的不可判定性圖靈機停機問題: 能否給出一個判斷任意一個圖靈機是否停機的一般方法? 答案是NO.這個問題實際上是問: 是否存在一臺"萬能的"圖靈機 H, 把任意一臺圖靈機 M 輸入給 H, 它都能判定 M 最終是否停機, 輸出一個明確的 "yes" 或 "no" 的答案? 可以利用反證法來證明這樣的 H 不可能存在. 假定存在一個能夠判定任意一臺圖靈機是否停機的萬能圖靈機 H(M), 如果 M 最終停機, H 輸出 "halt"; 如果 M 不停機, H 輸出 "loop". 我們把 H 當作子程式, 構造如下程式 P:function P(M) {if (H(M)=="loop") return "halt";else if (H(M)=="halt") while(true); // loop forever}因為 P 本身也是一臺圖靈機, 可以表示為一個字串, 所以我們可以把 P 輸入給它自己, 然後問 P(P) 是否停機. 按照程式 P 的流程, 如果 P 不停機無限迴圈, 那麼它就停機, 輸出"halt"; 如果 P 停機, 那麼它就無限迴圈, 不停機; 這樣無論如何我們都將得到一個矛盾, 所以假設前提不成立, 即不存在這樣的 H. 或者說, 圖靈機停機問題是不可判定的(undecidable).
圖靈機停機問題(The Halting Problem)的不可判定性圖靈機停機問題: 能否給出一個判斷任意一個圖靈機是否停機的一般方法? 答案是NO.這個問題實際上是問: 是否存在一臺"萬能的"圖靈機 H, 把任意一臺圖靈機 M 輸入給 H, 它都能判定 M 最終是否停機, 輸出一個明確的 "yes" 或 "no" 的答案? 可以利用反證法來證明這樣的 H 不可能存在. 假定存在一個能夠判定任意一臺圖靈機是否停機的萬能圖靈機 H(M), 如果 M 最終停機, H 輸出 "halt"; 如果 M 不停機, H 輸出 "loop". 我們把 H 當作子程式, 構造如下程式 P:function P(M) {if (H(M)=="loop") return "halt";else if (H(M)=="halt") while(true); // loop forever}因為 P 本身也是一臺圖靈機, 可以表示為一個字串, 所以我們可以把 P 輸入給它自己, 然後問 P(P) 是否停機. 按照程式 P 的流程, 如果 P 不停機無限迴圈, 那麼它就停機, 輸出"halt"; 如果 P 停機, 那麼它就無限迴圈, 不停機; 這樣無論如何我們都將得到一個矛盾, 所以假設前提不成立, 即不存在這樣的 H. 或者說, 圖靈機停機問題是不可判定的(undecidable).