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

144

|

第 5 章

規則

讓我們想像計算者執行的運算被拆成數個相當基本的『簡單運算』，簡單到不

容易想像它們能再進一步分割。[...] 運算實際的執行 [...] 是由計算者的心智狀

態和觀察到的符號所決定。尤其它們會在運算完成之後決定計算者的心智狀

態。

現在我們可以構建一部機器來執行這位計算者的工作。

—

艾倫圖靈，論可運算的數值，及其在可判斷問題的應用

（On Computable Numbers, with an Application to the Entscheidungsproblem）

我們可能希望圖靈機在每個運算步驟執行幾個『簡單運算』：在磁帶頭目前位置讀取字

元、在這個位置寫入新字元、往左或往右移動磁帶頭、或者更改狀態。設計一種不論什

麼情況都足夠靈活的單一格式規則（而不是讓所有的動作使用不同類型的規則），我們

就能予以簡化，就像我們曾替下推自動機做過的那些。

這種一致的規則格式有 5 個部分：

• 機器的目前狀態

• 必須出現在磁帶頭目前位置的字元

• 機器的下一個狀態

• 在磁帶頭的目前位置寫入的字元

• 在寫入磁帶之後移動磁頭的方向（往左或往右）

這裡我們假設圖靈機每次遵循規則都會改變狀態並將字元寫入磁帶。就如同狀態機的情

況，只要採用實際上不會改變狀態的規則，我們一定可以讓『下一個狀態』和目前的狀

態相同；類似的是，如果我們想要不改變磁帶內容的規則，可以只用一條寫入的字元即

為它所讀取的規則。

我們也假設磁帶頭在每一步驟一定都會移動。這在不移動磁帶頭的情況

下，就不可能寫入更新狀態或磁帶內容的單一規則，但若是編寫一條依所 ...