细胞自动机，那是什么东西？

细胞自动机

在上篇文章《神奇的生命游戏，是什么？》中，我们初步了解了什么是生命游戏。

这不，今天小菜和老鸟还在讨论呢。

老鸟：你知道么，生命游戏其实是一个二维的细胞自动机。

小菜：细胞自动机？听着好高大上啊，那是什么东西啊？

老鸟：细胞自动机，也叫元胞自动机，英文是 Cellular Automaton，很多文章中会把简写成 CA。元胞自动机是定义在一个由具有离散、有限状态的元胞组成的元胞空间上，并按照一定局部规则，在离散的时间维上演化的动力学系统。

小菜：能说人话么？

老鸟：哈哈哈。简单的来说，就是格子细胞按照规进行演化，而演化则是自动进行的，并不需要人工的干预。

我们再来回顾下生命游戏的规则：

• 人口过少，离群：如果一个活细胞少于两个活的邻居，它就会死亡。
• 正常：一个有两个或三个活邻居的活细胞可以延续到下一代。
• 人口过多，过度竞争：一个有超过三个活邻居的活细胞死亡。
• 繁衍：如果一个死细胞正好有三个活着的邻居，它就会复活。

“生命游戏的规则，不管你从哪里看到的，都是这样一个确定的描述。”老鸟补充说道。

老鸟：好了，今天我们不说二维，简单点，我们降维，来说一下一维，也就是一维细胞自动机。

小菜：好耶！

一维细胞自动机

老鸟：说到一维细胞自动机，必须要提到一个人物。

小菜：谁？

老鸟：Wolfram。

小菜：能介绍下么？

老鸟：Wolfram 原本是研究粒子物理和宇宙学的，但细胞自动机模拟出的复杂的类似真实自然界中某些现象和过程的图案激发了他对该领域强烈的兴趣。这个人认为生命游戏有一个缺点，就是只研究了一种规则，所以他系统研究了细胞自动机基于多种规则下的不同演化过程。

老鸟喝了口水继续说道：一个细胞有俩状态，黑和白，你认为生或死也是可以的，细胞的邻居就是细胞左右的相邻细胞。一个细胞和相邻的两个邻居组成了一个单元组。

老鸟：单元组有几个细胞？

小菜：3个嘛。

老鸟：那我再考察下你，这个单元组可能有多少种组合？

小菜：这个可难不倒我。每个细胞有两个状态，用 1 和 0 表示，单元组有 3 个细胞，所有的状态一共是 2 * 2 * 2，也就是 2 的 3 次方，一共 8 种排列组合。

边说边写，小菜在纸上排列出了所有可能性：

• 1 1 1
• 1 1 0
• 1 0 1
• 1 0 0
• 0 1 1
• 0 1 0
• 0 0 1
• 0 0 0

老鸟：不错嘛。中间就是当前的细胞，我们叫中心细胞吧，左右是它的邻居。一共是 8 种 状态，那我再问你，当前细胞下一步也是两种状态，不是 1 就是 0，按照上面列举的顺序，一共多少种可能性？

小菜：So easy。2 的 8 次方，也就是 256 种。

说完小菜便在纸上绘制出了一幅图

小菜接着说道：举个例子，比如 1 0 0，中心细胞状态是 0，左右邻居是 1 和 0，那么中心细胞 0 的下一代可能是 1 或者 0，两种状态，按照上面的排列顺序，就是 8 个 2 相乘，256 种。嘿嘿。

说完小菜得意的笑了。

老鸟：没错。256种可能性，于是关于规则，按照编号，有 Wolfram 规则 0，Wolfram 规则 1, Wolfram 规则 2, ···，Wolfram 规则 255。

老鸟：来看看 规则 90 如何？

小菜：走你～

规则 90

上图列举了一些比较出名的一些规则。规则 90 非常出名。

小菜：这些图为什么是这样的？你说的一维细胞自动机，不是一维直线么？

老鸟：你要注意了。咱们说的是一维，的确是一条线上的格子细胞，而细胞的演化会随时间不断进行，但为了更清楚的了解每一次演化的图形，所以每一次迭代，都往下面画一行，这样下来，多次迭代，就会形成二维图形，就像上图一样。

小菜：哦哦，原来如此啊。

老鸟：是的。规则 90 演化生成的图形就是著名的“谢尔宾斯基三角形”，以波兰数学家瓦茨瓦夫·谢尔宾斯基的名字命名，你看它是前阵子我们说的啥？

谢尔宾斯基三角形

小菜：分形！

老鸟：没错。神奇吧。

“这个规则演化下去，竟然会形成分形图案，真的太美妙了！”老鸟感慨道。

小菜的课后作业：

小菜使用 Processing 实现的规则 90 效果，运行在了 iPad 模拟器上。

规则 30

老鸟：规则 30 也比较出名。最后的图形

迭代的原理图展示：

一维细胞自动机就简单介绍到这里，读者朋友们对这方面感兴趣的可以使用搜索引擎进行探索。

更多阅读

• https://mathworld.wolfram.com/ElementaryCellularAutomaton.html[1]
• https://wizardforcel.gitbooks.io/think-comp-2e/content/5.html[2]

参考资料

[1]

https://mathworld.wolfram.com/ElementaryCellularAutomaton.html: https://mathworld.wolfram.com/ElementaryCellularAutomaton.html

[2]

https://wizardforcel.gitbooks.io/think-comp-2e/content/5.html: https://wizardforcel.gitbooks.io/think-comp-2e/content/5.html

小菜与老鸟后期会不定期更新一些 Processing 绘制的代码思路分析，欢迎关注不迷路。