元胞自动机
元胞自动机是一种离散的数学模型：一张由细胞组成的网格，每个细胞都有一个确定的状态，例如存活或死亡。所有细胞在同一时刻改变状态，依据一组固定的规则和直接相邻的邻居的状态。基本规则往往极其简单，却能长出复杂、有机且不可预测的图案。
四个基本部分
每个元胞自动机都由同样的四个部分构成。 网格是细胞所在的空间。它可以是一维的线、像棋盘一样的二维平面，甚至是三维空间。 状态是细胞可能处于的情况。最简单的情况下，细胞是二元的：黑或白，1 或 0。 邻域是直接影响一个细胞的那组细胞。在方格网格上，通常是摩尔邻域，即周围全部八个细胞；或冯·诺依曼邻域，即只有北、东、南、西四个。 规则是自动机的大脑：决定每个细胞新状态的逻辑。例如：如果我活着，但活邻居少于两个，我就会因孤独而死。每个细胞都在同一时刻应用同样的规则。
1. 康威生命游戏
规则：B3/S23。活细胞有 2 或 3 个活邻居时存活。死细胞恰好有 3 个活邻居时复活。其他所有细胞在下一代都是死的。 约翰·康威于 1970 年设计了它，马丁·加德纳在《科学美国人》上的专栏让它闻名于世。它会产生滑翔机、振荡器和飞船。同年，比尔·高斯帕发现了第一个滑翔机枪：一个每 30 代发射一架新滑翔机、永不停止的图案。生命游戏可以进行计算，因为滑翔机能携带信号，并像逻辑门一样相互碰撞。最重要的是，它展示了复杂行为如何从简单规则中生长出来。
2. 规则30
类型：一维初等元胞自动机。每个细胞的下一个状态取决于它自己和左右两个邻居，每一代都画成上一行下方的新一行。 斯蒂芬·沃尔夫勒姆于 1983 年提出了规则30。从单个黑色细胞出发，它会长出一个混沌的三角形。尽管规则是确定性的，它看起来却是随机的，随机到它的中间一列曾被用作伪随机数生成器。同类的三角形也出现在织锦芋螺贝壳的色素花纹中。
3. 规则110
类型：一维初等元胞自动机，和规则30 一样，只是由八个答案组成的表不同。 规则110 已被证明具有计算通用性：马修·库克证明，只要首行合适，它就能模拟通用计算机能完成的任何计算。它支持在重复背景上移动的结构，这些结构相遇时会相互作用。证明正是把这些碰撞用作逻辑。它展示了极其简单的规则如何能模拟任意计算。
4. Brian's Brain
状态：关闭、开启（激发）和不应期。 规则：关闭的细胞在恰好有 2 个邻居开启时开启。开启的细胞进入不应期。不应期的细胞变为关闭。 它由布莱恩·西尔弗曼设计。由于细胞激发后必须休息一代，每个脉冲都会不断远离它经过的地方。结果是一群自我推进的图案，类似可激发介质（如神经组织或心肌）中的波，常常看起来鲜活而有机。
5. Wireworld
状态：空、电子头、电子尾和导体。 规则：电子头变成电子尾，电子尾变成导体，当导体恰好有 1 或 2 个邻居是电子头时，导体变成电子头。空细胞保持为空。 Wireworld 也是布莱恩·西尔弗曼设计的，时间是 1987 年。导体细胞就是导线，一个电子头后面跟着一个电子尾，就是沿导线奔跑的电子。它可以模拟电子电路：一圈带一个电子的导线就是时钟，一个小缺口就是二极管，几个细胞就能组成逻辑门。人们已经在其中搭建出完整的计算机，例如戴维·穆尔和马克·欧文的 Wireworld 计算机，它能计算质数。
沃尔夫勒姆的 256 条规则和四个类别
一个有两个邻居的一维细胞会看到八种图案之一，从 111 到 000。一条规则为每种图案给出新状态，所以它是八个比特，共有 2⁸ = 256 条初等规则。把这八个答案读作一个二进制数，就得到规则的名字：规则30 是 00011110，规则110 是 01101110。 斯蒂芬·沃尔夫勒姆按照规则的行为，从有序到混沌对它们进行了分类。 1. 第 1 类会稳定在均匀状态。 2. 第 2 类会稳定为静止或重复的结构。 3. 第 3 类保持混沌，看起来是随机的，如规则30。 4. 第 4 类会在有序与混沌的边界上构建移动并相互作用的结构，如规则110。
难度排名
生命游戏 ★☆☆☆☆ · 规则30 ★☆☆☆☆ · Brian's Brain ★★☆☆☆ · Wireworld ★★★★☆ · 规则110 ★★★★★。前两个边看边就能明白。规则110 把它的移动结构藏在重复的背景里。
视觉上最美
1. Brian's Brain · 2. 康威生命游戏 · 3. 规则30 · 4. 规则110 · 5. Wireworld。
数学上最重要
1. 规则110：通用性 · 2. 生命游戏：通用性与涌现 · 3. 规则30：混沌与随机性 · 4. Wireworld：数字逻辑 · 5. Brian's Brain：可激发系统。
在自然、物理和密码学中
元胞自动机被用来模拟自然、物理和密码学中的复杂系统。这个想法可以追溯到 1940 年代的斯坦尼斯拉夫·乌拉姆和约翰·冯·诺依曼，他们用一张细胞网格设计了一台能复制自身的机器。 在现实世界中，你可以在一些贝壳的色素花纹中看到元胞自动机，例如织锦芋螺，它的三角形看起来像规则30；还有珠宝蜥的鳞片，它们按照一条接近元胞自动机的规则在绿色和黑色之间切换。物理学家用它们来模拟气体流动、沙堆和森林火灾。规则30 表面上的随机性使它成为随机数生成器和流密码的候选。
在 PictorX 中探索
打开元胞自动机，运行全部五种。观看滑翔机枪、一支飞船舰队，或者需要 1,103 代才能稳定下来的 R-五格骨牌。输入任意生命游戏规则，如 B36/S23，或 0 到 255 之间的任意初等规则编号。绘制和擦除细胞，让电子穿过 Wireworld 电路，环绕边缘，并切换到彩色模式。保存 PNG，或在 PictorX 编辑器中打开画布。
常见问题
什么是元胞自动机？
一张由细胞组成的网格，其中每个细胞都有一个状态。每一步，所有细胞按同一条固定规则一起更新，这条规则只看一个细胞和它的邻居。尽管规则简单，图案却可能复杂且不可预测。
元胞自动机是谁发明的？
斯坦尼斯拉夫·乌拉姆和约翰·冯·诺依曼，1940 年代在洛斯阿拉莫斯。约翰·康威的生命游戏（1970 年）让这个想法流行起来，斯蒂芬·沃尔夫勒姆在 1980 年代研究了 256 条初等规则。
哪些元胞自动机是图灵完备的？
在这里的五种中，规则110 和生命游戏已被证明是通用的，而 Wireworld 可以容纳一台完整的计算机。通用的意思是，只要初始图案合适，它们就能完成通用计算机能完成的任何计算。
沃尔夫勒姆的四个类别是什么？
第 1 类消亡为均匀状态，第 2 类稳定为静止或重复的结构，第 3 类保持混沌，如规则30，第 4 类构建移动并相互作用的结构，如规则110。
规则30 为什么看起来是随机的？
每一步都是确定的，但每个细胞都会把左邻居与另外两个细胞混合起来，这种混合方式会迅速扩散微小的差异。人们在它的中间一列中还没有找到任何简单的规律，所以它被用来生成随机数。
相关工具
元胞自动机
在浏览器中运行康威生命游戏、规则30、规则110、Brian's Brain 和 Wireworld。绘制细胞、修改规则，看简单的规则长出复杂的图案。
兰顿蚂蚁
在浏览器中运行兰顿蚂蚁。观察对称、混沌和 104 步的高速公路，再试试多色规则、多只蚂蚁、六边形网格和 Turmite。
乌拉姆螺旋
斯坦尼斯瓦夫·乌拉姆 1963 年的螺旋如何把整数排在方格上，素数为何聚集在二次式对角线上，以及螺旋从 41 开始时欧拉的四十个素数位于何处。
反应扩散实验室
绘制化学种子，观看 Gray–Scott 反应扩散生长出斑点、条纹、迷宫和珊瑚。调节补给、抑制、扩散与速度——然后保存 PNG。
了解更多分形知识
了解曼德博集、朱利亚集、牛顿分形与诺瓦分形如何生成——以及为何放大永远不缺细节。
准备好尝试了吗？
在浏览器中打开 PictorX — 无需安装，无需信用卡即可启动。
试试元胞自动机