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

終極機器

|

155

因此就如同有限自動機，決定論圖靈機可以模擬非決定論的版本。模擬物因為使用磁帶

儲存適當編碼的圖靈機組態佇列而得以正常工作，每個都包含模擬機可能的目前狀態和

磁帶。模擬物啟動時，磁帶只儲存一個組態，代表的是模擬機的起始組態。藉由讀取佇

列前面的組態、找到它適用的每條規則，並使用那條規則產生新組態（這些新組態會被

寫到佇列後面的磁帶），就可以執行模擬運算的每個步驟。只要完成了每條適用規則的

工作，就會刪除最前面的組態，而且此過程會和佇列裡的下個組態重新開始。模擬機的

步驟會不斷重複，直到佇列前面的組態代表的是已經達到接受狀態的機器。

這種技術允許決定論圖靈機以橫向優先的順序，探索模擬機的所有可能組態；如果有非

決定論機器可以達到接受狀態的任何方式，就算其他執行路徑會導致無窮迴圈，模擬物

還是會找到它。實際上，將模擬物實作成規則手冊需要很多細節，所以我們不會試著在

這裡完成，但事實上，這可能意謂著我們無法藉著增加非決定論而讓圖靈機的運算能力

更強大。

最大的運算能力

決定論圖靈機代表著運算機器從能力有限到全力運算的戲劇性轉折點。事實上，任何嘗

試升級圖靈機規格而讓它們更強大都會宣告失敗，因為它們已經能

模擬

任何潛在的增

強功能

3

。雖然增加某些功能可以讓圖靈機更小或更有效率，但無法給它們新的重要基本

能力。

我們已經看到為什麼這也適用非決定論，現在讓我們看看傳統圖靈機的其他 4 種擴充

（內部儲存空間、副常式、多重磁帶、多維磁帶），並且探討它們何以未能提高運算能

力。儘管涉及其中的若干模擬技巧相當複雜，但在最後它們都只是程式設計的問題。 ...