“活”過來的經典計算機

陳凱

如果有一臺機器，它所做的事情十分單一，就是把一個符號串中的一些字符替換成另外一些，反復替換后，這臺機器就能實現通用計算。換句話說，人們給通用計算機編寫的程序，都可以移植到這臺簡單的字符替換機器上。這聽上去讓人驚訝，但基于馬爾科夫算法（Markov algorithm）的字符串重寫系統（String Rewriting System）證明，這不僅在理論上可行，而且若真的想用這個系統來編寫程序實現特定任務，也不是特別難的事情。這個系統在理論計算科學的發展歷史中具有很重要的意義。

為了方便大家理解，這里先舉一個簡單的例子。假設有一個字符串，它只能由“[”“a” “b”“0”“1”“]”這六個符號組成，按以下規則替換：若看到“0a”就替換成“ab0”，簡寫成0a->ab0，另外幾條規則分別是0b->a0、0]->1]、b1->1b、a1->1a、[1->[0。注意在替換時，優先匹配靠前的規則，也就是說，替換時先看寫在前面的規則，若前面的規則沒能匹配到，再一條條規則往后看。

如果初始的字符串是[0a]，那么會有怎樣的結果？如果人工來替換實在太辛苦，所以可以借用馬爾科夫算法模擬機Yad Studio來進行實驗，這款軟件（如圖1）可在網絡上免費下載到。馬爾科夫當年構建這個重寫系統的時候，可沒有那么方便的工具可使用。

圖1中代碼第1行T={[，a， b，0，1，]}其實規定了可用的符號，從第2行到第7行就是替換規則。可以看出，第一步，[0a]變成了[ab0]，第二步后變成了[ab1]，第三步后變成了[a1b]，一直做下去會有什么結果呢？仔細觀察后可知，當符號“0”和“[”碰到一起時，字符a和b的總數量分別是1、1、2、3、5、8、13、21……這就是斐波拉契數列。這六條替換規則，其實就生成了斐波拉契數列。

如果說不愿意去一個一個地數字符的數量，還可以試試另外一套規則，把字符數量以數碼的形式顯示出來，接下來的程序會將“[”和“]”之間的“a”的數量轉化成二進制數。將規則寫到Yad Studio中是圖2所示的樣子。

如第72頁圖3所示，第1行規定了可用符號，第2行規定了替換結束的條件。如果初始字符串是[*aaaaaaaaaa]，那么替換了25步后會自動結束：得到的結果是“$1010”，“1010”恰好是字母a的個數的二進制數，很奇妙不是嗎？

這里給大家一些值得挑戰的任務。例如，試著用馬爾科夫重寫系統，實現加、減、乘、除的運算，然后把不同的運算結合在一起；或者用這個系統來演算西拉古斯問題（Syracuse problem），即反復對某數進行如下操作：如該數為偶數則除以2，如該數為奇數則乘3加1，看需要多少步，最終數字會成為1。這就需要想辦法，用重寫系統將分支結構和循環結構整合在一起。（答案在本期找）