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

148

|

第 5 章

決定論

設計成決定論的特定圖靈機，則必須遵守和決定論下推自動機相同的限制（請見第 116

頁的『決定論』），然而這次我們不必擔心自由移動，因為圖靈機沒有這種機制。

圖靈機下個動作的選擇，是根據它的目前狀態和目前在它磁帶頭下的字元，因此決定論

機器對狀態和字元的每種組合只能有一條規則（『無矛盾』規則），這是為了防止它下一

個動作有任何的模糊。為了簡單起見，我們將放寬『無遺漏』規則，正如我們在 DPDA

所做的，並且假設若無適用規則，機器可以進入絕對的停止狀態，而非堅持每種可能的

狀況它都必須有對應的規則。

模擬物

我們已經清楚瞭解決定論圖靈機應該如何運作，現在讓我們建置 Ruby 模擬物以便觀察

它的實際運作。

第 1 步是實作圖靈機磁帶。雖然這項實作物很明顯的必須儲存那些寫入磁帶的字元，但

是也需要記住磁帶頭目前的位置，才能讓模擬的機器可以讀取目前字元、在目前位置寫

入新字元，並且將磁帶頭左右移動而到達其他位置。

完成這件工作的簡潔方式是將磁帶分成 3 個獨立的部分（磁帶頭左側的所有字元、磁帶

頭底下的單一字元、磁帶頭右側的所有字元），並且分別儲存每個部分。這會讓它很容

易就能讀取和寫入目前字元，而在這 3 個部分之間隨意移動就能移動磁帶頭；例如向右

移動一個方塊，意謂著目前字元會變成磁帶頭左側的最後一個字元，而且磁帶頭右側的

第 1 個字元會變成目前的字元。

我們的實作物也必須維持磁帶無限長並填滿空白方塊的錯覺，但所幸為此我們不需要無

限大的資料結構。在任何指定時刻可以讀取的唯一磁帶位置，是在磁帶頭底下，因此只 ...