問題解決：停機問題

停機問題

在現代計算的早期，一位名叫艾倫·圖靈的英國學者提出了停機問題。這個問題與我們是否能夠確定一個程式最終會停止執行還是永遠執行有關，例如

console.writeline("hello")

將寫入螢幕，然後停止。但是，看一下

dim x as integer = 9
while x > 8
  console.writeline("hello")
end while

這將永遠不會結束，它永遠不會停止，因為 x 始終大於 8，並且永遠不會變小。這意味著 while 迴圈將永遠持續下去，不斷地打印出“hello”。在這兩個所示示例中，很容易判斷程式是否會停止，但並非所有程式都如此容易。想象一下，我們得到了一段更復雜的程式碼

dim x as integer = 9
dim total as integer = 0
while total < 100
  total = total + x
  x = x / 2
end while

這更難，但仍然可以透過更多思考和處理器上的更多時間來解決。我們可能會得到一段需要數週、數年甚至數千年才能完成的程式碼。但我們如何知道所有程式都會結束還是不會結束？為了確定程式是否停止，我們

• 執行一個程式，輸入一個給定的輸入，如果它停止，我們就知道它停止了
• 但如果它在合理的時間範圍內持續執行，我們不能斷定它會永遠迴圈（也許我們還需要再等一段時間……）

我們當然可以建立一個數學證明來確定程式碼是否會結束，我聽到你說。那麼讓我們證明恰好相反

停機解決方案 H 接受一個輸入程式 A 和一組輸入 X，然後它確定該程式是否會完成執行或不會。

您可以用程式 A 的副本替換輸入 X。由於程式 A 是由程式碼組成的，因此可以將其轉換為 1 和 0，從而為 H 提供資料輸入。

讓我們建立一個程式 K，如果 H 的結果是停止，它將永遠迴圈，如果 H 的結果是永遠迴圈，它將停止。

function K(i):
    if H(i,i) = halt then
        loop forever
    else
        halt

如果 H 說停止，K 將迴圈。如果 H 說迴圈，K 將停止，因此停機解決方案 H 將是不可判定的

因此，我們可以看到，存在諸如 K 之類的程式示例，我們無法確定它們是否會永遠停止。

• 瞭解更多關於停機問題的資訊