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

四處皆通用

|

251

010010

10010

00101

0101

101

=> nil

因此，事實證明，當這個系統開始使用字串

11

時，系統

的確

存在著重複的行為：在不

穩定的起始階段之後，9 個連續字串的模式出現（

101, 010010, 10010, 00101, …

），而且

永遠自我重複。當然，如果我們改變起始字串或任何規則，長期行為將有所不同。

循環標籤系統非常有限（它們的規則僵硬死板，只有兩個字元，而且刪除數可能最

少），但讓人驚訝的是，還是可能使用它們來模擬

任何

標籤系統。

依據循環標籤系統的一般標籤系統，其模擬物的運作方式如下：

1. 決定標籤系統的

字母表

（

alphabet

），也就是它所使用的字元集。

2. 設計編碼方案，讓每個字元能與適用於循環標籤系統的唯一字串相關聯（也就是只

包含

0

和

1

）。

3. 將它所附加的字元予以編碼，將原始系統的每條規則轉換成循環標籤系統的規則。

4. 以空規則填入循環標籤系統的規則手冊，藉此模擬原始標籤系統的刪除數。

5. 對原始標籤系統的輸入字串進行編碼，並將它當作循環標籤系統的輸入來用。

讓我們藉著實作它們而讓這些想法更為具體。首先我們需要能詢問標籤系統所使用的字

元為何：

class TagRule

def alphabet

([first_character] + append_characters.chars.entries).uniq

end

end

class TagRulebook

def alphabet

rules.flat_map(&:alphabet).uniq ...