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

164

|

第 5 章

編碼格式的精確細節並不重要，只要它能滿足這些目的。為了提供範例，一種可能的格

式使用

一元

（

unary

）

5

表示法編碼，將不同的值編碼成單一重複字元（例如

1

）的不同

大小字串：如果模擬機器使用字元

a

、

b

、

c

，那麼就能以一元的形式將這些編碼成

1

、

11

、

111

。另一個字元，例如

0

，可以用作分隔一元值的標示符號：字串

acbc

可以表示

成

101110110111

。這不是很省空間的格式，但只要在磁帶儲存越來越長的

1

字串，就能

將它擴展而可容納任意數量的編碼字元。

只要我們決定了如何編碼單一字元碼，就需要一種方式來表示模擬的圖靈機的規則。如

果要完成這樣的工作，我們可以針對規則的個別部分（狀態、字元、下個狀態、欲寫入

的字元、欲移動的方向）進行編碼，並且在需要的地方使用特殊的分隔符號字元將它們

接合到磁帶。在我們的範例編碼格式，雖然可以使用專用的字元來表示左和右（例如

L

和

R

），但是也能以一元的形式表示狀態（狀態 1 是

1

、狀態 2 是

11

，等等），因為我們

知道總共只有兩個方向。

我們可以將個別的規則接合在一起，以此表示整個規則手冊；同樣的，將它目前狀態的

表示和它目前磁帶內容的表示接合在一起，我們可以對模擬機器的目前組態進行編碼

6

。

這給了我們想要的：在另一部圖靈機的磁帶寫成一組字元的完整圖靈機，準備以模擬帶

來活力。

模擬物

基本上，UTM 的運作方式和我們在第 148 頁『模擬物』所建置的 Ruby 模擬物相同，

差別只在 UTM 更加費力。

模擬機器的描述（它的規則手冊、接受狀態、起始組態）以編碼的形式儲存在 ...