冯诺依曼元胞自动机.docx

冯诺依曼元胞自动机(John Von Neumann’s Cellular Automaton)冯诺依曼元胞自动机是由计算机科学家约翰冯诺依曼发明的一种图灵完备的元胞自动 机目前它还有三种不同的规则，分别名叫：JvN29，Nobili32,Hutton32.可以模拟许多“机 器”，比如自我复制机（Replicator）就是其中最重要的一种目前几乎没有介绍冯诺依曼元胞自动机的中文网站，所以我在此给大家比较详细地介绍 一下它一、JvN29这是由John Von Neumann在1940年发明的自动机由于其上的活细胞共有29种状态， 故名JvN29，29种状态分别为：史I金旗制葬牛0个■►个+ .l-l个|*|.»|个前8种和后3种是激发态（不稳定），不用记其中4个蓝箭头和4个红箭头相当于“导线”，4个绿箭头和4个紫箭头分别是两种电线中 的“电流”紫箭头可以eat （即将其变为死细胞，下同）蓝箭头，绿箭头可以eat红箭头不过紫箭头 权限更高，它还可以eat掉4种菱形当一串绿箭头或紫箭头到达“导线”最前端时，前端前的死细胞就会根据绿箭头或紫箭头的 不同序列而变成不同的稳定活细胞，这个过程叫做翻译，需要用到前8种激发态作为桥梁。

8种激发态间有一个转化关系，如图：我们一般采用所谓“密码子”的箭头序列在JvN29中，每种稳定细胞都对应一个密码子， 即一个可以产生此种细胞的箭头序列从上图可以总结出JvN29的密码子如下：这个表同样适用于红箭头和紫箭头菱形是种重要的状态，根据“导线”的不同接法它可以发挥不同的作用1）当接为一入多出时，菱形充当信号分路器：当单独信号输入时当两个信号输入时:可见，在分路时信号会延迟，菱形的三种激发态充当了桥梁的作用，2）接入为三入一出或二入二出时，菱形充当“与门”，当且仅当发输入端全都有信号来时， 菱形才进入激发态3）特殊地，若接入一入一出，就构成信号延迟器:JvN29有一个缺点：它不允许直接信号交叉，若要实现，要用到一种信号交叉器:这种交叉器有缺陷，第一是竖直导线只能向上，水平导线只能向右，第二是水平信号和竖直 信号不能同时进入，否则会出错二、Nobili32为了弥补JvN29不允许信号交叉的缺陷，Renato Nobili于1994年在JvN29的基础上增加了 三种菱形的状态:，从而发明了 Nobili32，要实现交叉，只需在交叉处放上一个菱形即可，如:当横方向信号穿过时，菱形变为当竖方向来时，菱形变为两个方向同时来时，变为Nobili32还给菱形的三个非交叉激发态增加了一个衰变条件：当且仅当有接出的导线时才衰 变。

在JvN29和Nobili32中还有几个比较重要的东西：1）编码器（coder）为了使密码子的产生更加简单，在大型机器中一般使用coder每种密码子可对应一个coder， 当输入一个绿箭头时，就会输出其密码子如向下的蓝箭头的coder就是：2）译码器（decoder）有些时候，为了识别某种信号序列，我们会用到decodero Decoder有两种，一种是完全的， 一种是不完全的完全decoder是要求输入信号满足它是decoder需要识别的充要条件，不 完全decoder则满足必要不充分条件如一个序列满足它是向下蓝箭头密码子的充要条件是 “第一位是1，第二位是0，第三位是1，第四位是0”，必要不充分条件是“第一位和第三 位都是1”3） C-Arm在JvN29和Nobili32中为了能用机器产生一些单独存在的细胞，就是用到C-Arm, JvN29 中的和Nobili32中的有所不同：Nobili32：+ + + + + +现以Nobili32为例描述一下工作过程:刖进:i建造：把密码子通入红箭头，再后退4） R-Arm有了 C-Arm,就还需要有控制器来控制控制器是受控于ROM中存储的信息。

在ROM中, 需要有信息的读取装置，就是R-Arm信息以类似于二进制的方式储存在水平直线（纸带）上，“0”是死细胞，“1”是向下蓝箭头:读取时，向蓝箭头输入如果是0，则会消耗一个密码子而返回一个绿箭头；如果是1，则返回三个绿箭头，最后使返回信号进入decoder来判断箭头个数，让C-Arm和R-Arm去完成相应的操作思考：R-Arm具体是怎样工作的？有了以上4种材料，就可以制作Replicator 了王要有两条思路：一是用一个循环带（） 储存信息，通过完全decoder来控制C-Arm复制自己，如JvN-Loop-Replicator，二是用R-Arm 和纸带控制，如NP-Replicator,N-Compressed-Replicator等但复制方法基本固定，前者是先复制机器，再复制遗传信息，后者则相反但用JvN29和Nobili32制作的Replicator不是 长，就是纸带长，完全复制需要101以上代，而且一次只能复制个，有一定局限性三、Hutton32为了使Replicator更小，复制得更快，Tim Hutton于2008年将Nobili32作了一个大的修改（看来还是最新产品），发明了另一种规则，名叫Hutton32在Hutton32中，一根蓝导线就可当作C-Arm。

和上面两种自动机相似，Hutton32也有9种基本密码子，但这些密码子最终形成的细胞还和 导线前端蓝箭头的方向有关其中4种称为C-Arm控制密码子：前进向右转±±向左转和之前两种自动机不同，这些密码子在Hutton32中不适用红导线之后会进一步介绍为了使蓝导线能当作C-Arm,Tim Hutton又增加了 9种Construct扩展密码子：作用前进蓝箭头翻译姑果右转蓝箭头 左转蓝箭头 掉头蓝箭头 向前红箭头 掉头红箭头□□□□□!sal ±±±±±_^这些密码子规定起来容易，实现起来难为此Tim Hutton增加了几条规则：1）在Hutton32中，紫箭头可以eat蓝箭头和菱形，绿箭头虽可以eat红箭头，但如果一个 指向红箭头的蓝箭头下一代将变成绿箭头，那它下一代就会被eat，如：这也就是说，你不能直接用绿箭头eat红箭头，而应先把蓝箭头所指的红箭头变成紫箭头， 再让绿箭头去eat；2） 当一个绿箭头的前面是死细胞，后面是蓝箭头时，它的下一代就变成紫箭头；3） 如果一个紫箭头前面是前7种衰变态，后面是蓝箭头，那么下一代它就会不变；4） 如果一个菱形紫箭头前面是蓝箭头或红箭头或菱形，后面是绿箭头，它的下一代就变成 死细胞；5） 一个前面是前七种衰变态后面是蓝箭头的紫箭头，下一代会变成与后面蓝箭头同向的蓝 箭头。

这样，这些密码子就巧妙地实现了红导线不能翻译密码子，当紫箭头到达最前端时，会在一代内产生一个和红导线方向一致的 蓝箭头： ＞噬国里里里里！:计数器(Counter)五位二进^Counter :个T .^1个个个个个个 个个+ 个 tt 中 个个中 个个0-> -►来分析一下他们：1）二进制 Counter信号从左边进入，在缺处形成一个蓝箭头:相当于二进制数WW1当又有信号来时，会在下一个缺口处形成一个蓝箭头，而刚才形成的蓝箭头会被红箭头eat， 这个过程叫进位：就好像二进制加法一样当所有的缺口都被蓝箭头填满后，下一个信号就会从右边输出，并 把Counter归零2）十进制 Counter：原理一样，只是每10个一进位Hutton32中，从◊接出的蓝箭头至少需有两个，如果只有一个，那么当有信号来时，蓝箭头 就会变成紫箭头，继而变成红箭头，而红箭头无法进行密码子翻译这就是Hutton32的一 个漏洞Hutton32中的Replicator也有两种不同的类型两种类型都是用tape储存遗传信息，利 用tape制造出一个辅助复制机，辅助复制机再制造出一个tape，再进行遗传信息两种类 型的tape不同，其一是一维的tape，其二是二维tape。

由于Hutton32的密码子具有旋转对 称性，所以可以在tape的出口处用◊分岔，实现一次同时复制出两个Hutton32中的Replicator复制速度普遍很快（相比于JvN29和Nobili而言），基本上可以在2 105代以内完成一个子代的复制目前最快的是Tim Hutton设计的Hutton_Replicator,Golly（最新版本为2.4），可以模拟包括冯诺依曼元胞自动机在内的多最后，推荐一款软件：种元胞自动机，速度很快，还自带有上面提到的NP-Replicator,N-Compressed-Replicator等 Replicator的rle文件想下载的朋友请到英文维基百科上搜索“Cellular Automaton”，在 External links里面就有下载，进入后点Download或者直接下载地址：二点谢谢大家!。