论文部分内容阅读
如果有一台机器，它所做的事情十分单一，就是把一个符号串中的一些字符替换成另外一些，反复替换后，这台机器就能实现通用计算。换句话说，人们给通用计算机编写的程序，都可以移植到这台简单的字符替换机器上。这听上去让人惊讶，但基于马尔科夫算法(Markovalgorithm)的字符串重写系统（StringRewritingSystem）证明，这不仅在理论上可行，而且若真的想用这个系统来编写程序实现特定任务，也不是特别难的事情。这个系统在理论计算科学的发展历史中具有很重要的意义。