“活”过来的经典计算机——马尔科夫重写系统  

作　　者：陈凯[1] 

机构地区：[1]上海市位育中学

出　　处：《中国信息技术教育》2017年第5期31-31,72,共2页China Information Technology Education

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

关 键 词：通用计算机 重写系统 马尔科夫 程序实现 字符串 发展历史 计算科学 机器 

分 类 号：TP311.1[自动化与计算机技术—计算机软件与理论]