“活”过来的经典计算机

陈凯

如果有一台机器，它所做的事情十分单一，就是把一个符号串中的一些字符替换成另外一些，反复替换后，这台机器就能实现通用计算。换句话说，人们给通用计算机编写的程序，都可以移植到这台简单的字符替换机器上。这听上去让人惊讶，但基于马尔科夫算法（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。这就需要想办法，用重写系统将分支结构和循环结构整合在一起。（答案在本期找）