1D Cellular Automata
在简单的规则之下为什么总是隐藏着复杂异常的表现? 一维元胞自动机(1D Cellular Automata)或许就是一个典型.
一维元胞自动机(1D Cellular Automata) 由一个长度为N的有限序列构成, 假设一台元胞自动机为 ca{0,0,0,0,1,1,1,0,1}, 由此可见, 每一个元素都有两个邻居, 因此在这台ca中可以得到 {0,0,0}, {0,0,0}, {0,0,1}, {0,1,1}, {1,1,1}, {1,1,0}, {1,0,1} 这些组合. 很明显的是, 这些组合的总数就是从二进制的000开始至111, 因此共有8种可能的组合. 而这8种组合又各自对应了0或1的一种状态, 比如某一台ca的规则为: {0,0,0}->0, {0,0,1}->1, {0,1,0}->1, {0,1,1}->1, {1,0,0}->0, {1,0,1}->1, {1,1,0}->1, {1,1,1}->0. 那么这些规则就决定了下一代的状态. 同样下一代继续遵循这些规则继续生长.
由此可见,规则共有从二进制的00000000开始至11111111, 总共256条规则. 我们也可以将其命名为第 1台元胞自动机规则是00000000, 第 2台元胞自动机是00000001... 这样我们就得到了256台一维元胞自动机, 它们中的大多数表现是可以想象的---没有任何值得注意的地方. 但是有一些元胞自动机的行为却非常复杂, 左上图是第 111(十进制)台元胞自动机的部分截图, 从图中可以看见周期性与非周期性结构的同时存在. 点击上图可以察看完整的 256台元胞自动机的表现. 点击 http://arc.net.cn/dl/cellular.tar.bz2 下载源程序.
最后必须要提及的是, "A New Kind of Science" 这本一千多页的著作, 它由Stephen Wolfram耗时10年完成, 它的官方在线版本的地址是: http://www.wolframscience.com/nksonline/toc.html . 在此书中 Stephen Wolfram 对各种 Cellular Automata 做了详细的分析, 他甚至宣布找到了这个世界的最根本规则---"一台元胞自动机(Cellular Automata)". 我对这个观点持以保留, 但是非常欣赏 Wolfram 创造性的工作. 同时欢迎您的观点 http://algo.net.cn/bbs/