深入理解運算原理｜從簡單的機器到無所不能的程式

不可能的程式

|

283

那麼，我們每次都能完成嗎？是不是總有聰明的方式能潛入問題，並找到以有限的時間

實作出保證能解決問題的機器或程式？

嗯…，不，不幸的是並沒有。有許多決定性問題（

無限

多），事實證明，它們之中有很

多都是無法決定的：並沒有保證停止的演算法能解決這些問題。這些問題每個都是無法

決定的，不是因為我們還沒有找到正確的演算法，而是因為問題本身根本不可能解決某

些輸入，而我們甚至可以證明不會找到合適的演算法。

停機問題

許多無法決定的問題涉及到機器和程式在執行過程中的行為。其中最著名的是

停機問

題

（

halting problem

），它的任務是決定具有特定初始磁帶的特定圖靈機，其執行是否

將會永遠停止。由於通用，我們可以用更實際的詞彙重新敘述同樣的問題：指定包含

Ruby 程式原始碼的某個字串，而且從標準輸入讀取該程式的另一個資料字串，執行該

程式最終會得到答案抑或只是無限循環？

建置停機核對器

不明白為什麼要將停機問題視為無法決定，畢竟很容易就能針對可以解決的問題提出個

別的程式。以下的程式無論它的輸入字串為何，都一定會停止：

input = $stdin.read

puts input.upcase

我們假設

$stdin.read

就是會立刻傳回某個值（也就是每個程式的標準輸

入皆為有限和非阻擋），因為我們感興趣的是此程式的內部行為，而非與

作業系統的互動。

相反的，小小的加些東西到原始碼，會產生明顯不會停止的程式：

input = $stdin.read

while true

# do nothing