“活”過來的經(jīng)典計算機

陳凱

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

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

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

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

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

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

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