圖靈機停機問題

Question

我正在尋找圖靈機停機問題的簡單解釋。我對這個話題很陌生，但我知道TMs是如何工作的基礎，他們是如何枚舉事物，機器配置等的，但我沒有很好地處理暫停問題。

有人可以提供一個很好的解釋這個話題嗎？

Answer 1

讓我們忽略圖靈機的世界，只考慮計算機程序。這會使我們的推理不那麼嚴格，但可能更容易遵循。

考慮以下任務：編寫一個程序，給定程序P和該程序的輸入，確定在給定該輸入時程序是否終止。 （爲了簡單起見，我們假定程序不要求用戶輸入，也不涉及隨機性，因此在同一輸入上運行相同的程序總是會執行相同的操作）。是否有可能編寫符合此描述的程序？答案是不。爲了表明這一點，我們將使用一個證明，通過與相抵觸。我們會假設，某人設法編寫程序，然後證明如果發生這種情況，會發生一些可怕的事情。

想象一下，有人寫一個函數，看起來像這樣：

function willHalt(program, input) 

該功能具有以下特性：

1. 它總是返回一個值。
2. 如果該函數返回true，那麼在指定的輸入上運行時，指定的程序最終會終止（暫停）。
3. 如果該函數返回false，則指定的程序在指定的輸入（循環）上運行時永不終止。

在這一點上，我們可以開始懷疑誰寫這個函數。

他們：「嘿！我剛寫了一個程序，可以接受任何程序和輸入，它會告訴你程序是否停止輸入！

我們：「真的嗎？它可以在任何程序？任何程序呢？」

他們：「是的！這就是我所說的。」

我們：「那麼，這個程序在這裏？

然後我們給他們這個程序：

function trickyTricky(input) { 
    /* Ask whether this program (named trickyTricky) is going to halt 
    * on its input. 
    */ 
    if (willHalt(trickyTricky, input)) { 
     /* If so, loop infinitely! */ 
     while (true) { } 
    } else { 
     /* If not, do nothing and stop running! */ 
    } 
} 

讓我們想想這個程序做什麼。

• 首先，想象一下，當給定一個特定的輸入時，這個程序最終會在該輸入上運行時終止。仔細追蹤程序，看看會發生什麼。首先，它詢問willHalt它是否會終止，答案是「是的，是的，它會。」這意味着if語句的計算結果爲true。所以程序進入無限循環！糟糕 - 該計劃本應停止，但它無限循環！

• 其次，假設這個程序在給定特定輸入時進入無限循環。仔細查看程序，看看會發生什麼。首先，它詢問willHalt它是否會終止。答案是否定的，所以它不進入if語句，而是立即完成運行。但這並不好 - 該程序應該無限循環，但它終止了！

所以現在我們有一個問題。如果你真的可以編寫一個函數來告訴你程序是否會停止某些輸入，那麼你可以使用該程序來構建一個與它應該做的事情相反的程序 - 這是不可能的！

停止問題只是形式化上述想法的一種數學上嚴格的方式。我們不談論程序，而是談論圖靈機和TM編碼。真的，數學背後的核心思想就是上面所展示的。

如果您有興趣，對於我去年教過的班級，我將a guide to self-reference and undecidability放在一起，這可能會讓您更深入地瞭解這種說法的方式。

Answer 2

暫停問題要求我們確定給定輸入的程序是否會停止（達到最終狀態）。圖靈證明，沒有任何算法可以確定任何給定的程序和輸入。

算法可能花費任意長的時間來處理程序及其輸入，但是對於所有程序和所有輸入，該算法無法準確確定程序是否最終會停止。隨着國家的每次變化，下一次都可能是最後一次。

暫停問題是decision problem的早期示例。

因爲沒有算法可以準確地回答'是的，它會停止'或'不，它不會暫停'停止問題，它不可能。