1.1 定义与核心思想
元胞自动机是一种在离散时空框架下运行的计算模型。其核心思想可概括为：大量简单、相同的个体（元胞）在一片规则网格上排列，每个元胞仅根据自身及其紧密邻域内其他元胞的当前状态，按照一组全局一致的局部规则同步更新为下一时刻的状态。尽管局部规则极其简单，系统整体却可能演化出极为复杂的、不可预测的模式，这一现象常被总结为“简单规则涌现复杂行为”。元胞自动机因此成为研究自组织、涌现计算和复杂系统科学的基础工具之一。
1.2 历史沿革
1.2.1 冯·诺依曼与自我复制机
元胞自动机的概念可追溯至20世纪40年代。计算理论之父约翰·冯·诺依曼（John von Neumann）为研究“自我复制机器”的抽象逻辑，设计了一种包含29种状态的二维元胞自动机模型。该模型旨在证明：只需遵循一组确定的局部规则，一个自动机能够复制出自身的精确副本。冯·诺依曼的工作为后来计算普适性提供了早期范例，但其模型因状态过多而难以直观操作。
1.2.2 康威的生命游戏诞生
1970年，英国数学家约翰·康威（John Conway）发明了名为“生命游戏”（Game of Life）的二维元胞自动机。康威大幅简化了冯·诺依曼的模型：仅用两种状态（“存活”与“死亡”）和一条简单规则（23/3规则，即一个存活元胞若其2或3个活邻居则继续存活，一个死元胞若有恰好3个活邻居则复活）。生命游戏立即在计算机爱好者和数学家中引发热潮。玩家们通过调整初始图案，发现了大量复杂结构——包括稳定块、周期振荡器以及沿网格移动的“滑翔机”。马丁·加德纳在《科学美国人》的“数学游戏”专栏中介绍生命游戏后，它成为元胞自动机乃至整个复杂系统领域最具标志性的模型。
1.2.3 沃尔夫勒姆的《一种新科学》
20世纪80年代，物理学家斯蒂芬·沃尔夫勒姆（Stephen Wolfram）开始系统研究一维元胞自动机。他提出了以规则编号系统为核心的理论框架，并通过计算机实验，将一维元胞自动机的行为归纳为四个基本分类。2002年，沃尔夫勒姆出版了篇幅巨大的《一种新科学》，主张将元胞自动机作为一种全新的科学范式，用以解释宇宙中从雪花到生物演化的各种复杂性。尽管该书在学术界存在争议，但它极大地推动了元胞自动机在大众文化中的认知度。
2.1 元胞与网格
2.1.1 一维、二维与三维网格
元胞自动机的基本空间结构是网格，网格的维数决定了元胞排列的形式。
- 一维网格：元胞排成一条直线（链），每个元胞通常有两个左右邻居。一维自动机便于分析，沃尔夫勒姆的规则集均基于此。
- 二维网格：元胞排成平面网格（如正方形方格、六边形网格等）。这是生命游戏和大多数物理模拟的默认空间，视觉效果丰富。
- 三维网格：元胞位于立方体晶格点中。三维自动机具有更多邻居（6个面贴邻、12个棱接、8个角接等），计算复杂度急剧上升，但因更贴近真实三维空间，在材料科学和流体力学中有应用。
2.1.2 边界条件（周期、固定、反射）
有限网格上的元胞在边界处如何与邻居交互，由边界条件决定。常用类型包括：
- 周期边界：网格首尾相接（一维环面、二维面包圈面），元胞在世界边缘的邻居跨越到对面，模拟无限空间而无截断。
- 固定边界：边界外的邻居状态被固定为某个常量（通常是死态或0），适用于模拟被刚性壁包围的系统。
- 反射边界：边界外邻居状态被视为边界内侧对称位置的元胞状态，产生类似镜面反射的效果。
边界条件对系统的长期演化有显著影响，选型需根据具体应用场景。
2.2 邻居与邻域
2.2.1 冯·诺依曼邻域
在二维网格中，冯·诺依曼邻域定义为：中心元胞的上、下、左、右四个正交相邻元胞，总邻居数为4。该邻域常用于模拟扩散或自旋系统。
2.2.2 摩尔邻域
一维邻域通常包含左右两个邻居。但在二维网格中，摩尔邻域包括了中心元胞周围全部八个相邻位置（上、下、左、右、四个对角），总邻居数为8。生命游戏即采用摩尔邻域。摩尔邻域使运动方向更丰富，能支持滑翔机等对角移动结构和旋转对称性。
2.2.3 广义邻域与半径
广义上，邻域半径r可大于1，称为“多邻域”或“扩展邻域”。例如一维邻居半径为2时包括左右各两个细胞；二维中半径2的摩尔邻域包含半径≤2的所有24个细胞。增大邻域半径会增加规则表的长度，从而允许更复杂的局部交互模式。
2.3 状态集
2.3.1 二元状态（0/1）
最简单、最常见的情况是每个元胞只有两种可能状态：通常记为0（死亡、空洞）和1（存活、填充）。生命游戏和大多数经典一维规则都属于二元状态。
2.3.2 多值状态与颜色
状态数可以是大于2的有限整数，比如冯·诺依曼的29状态自复制机，或模拟三态感染模型（易感-感染-恢复）。状态可以映射为不同颜色以便可视化，多状态自动机常用于模拟化合物浓度或交通流量。理论上，多状态自动机的规则可以编码更复杂的信息，但参数空间也随之爆炸。
2.4 更新规则
2.4.1 规则表与规则编号（沃尔夫勒姆编码）
对于一维二元状态、邻居半径为1的元胞自动机，每组中心元胞与左右两个邻居的3位二进制组合（共2^3=8种组合）对应一个输出状态。将8种组合的输出按二进制顺序排列成8位二进制数，即可获得0~255之间的唯一规则编号。例如规则110（二进制01101110）意味着当邻居配置为111、110、101、100、010时输出0，其余配置输出1。这种编号方式使规则的引用与重现变得简洁精确。
2.4.2 同步更新与异步更新
- 同步更新：全网格所有元胞在同一时刻统一读取当前状态、计算下一状态，同时完成更新。这是经典元胞自动机的标准模式。
- 异步更新：元胞在不同时间步更新，更新顺序可以是随机、循环或按需触发的。异步更新能更好地建模真实物理过程（如随机扩散）或分布式系统，但通常会导致自组织行为减弱甚至消失。
2.4.3 确定性 vs. 随机规则
- 确定性规则：给定相同的局部邻居配置，输出唯一确定。大多数经典自动机（包括生命游戏）属于此类。
- 随机规则：输出并非完全确定，而是按一定概率选取不同状态。例如，一个死细胞在邻居中有3个活细胞时，有80%概率变为活——这增加了系统的随机噪声，可用于模拟热力学涨落或遗传变异。随机性可能破坏精细结构，也可能帮助系统跳出局部静止态，是连接自动机与统计力学的桥梁。
3.1 一维元胞自动机
3.1.1 规则30：混沌生成器
规则30（二进制00011110）是沃尔夫勒姆最著名的发现之一。从单个活元胞（中心一个1）开始，规则30产生一个左半部分规则、右半部分完全混沌的三角形图案。其时间序列的随机性极强，以至于沃尔夫勒姆公司曾将其用作Mathematica软件的伪随机数发生器。规则30证明，非常简单的局部规则就能生成无法预测的复杂动态。
3.1.2 规则110：计算普适性
规则110（二进制01101110）在20世纪90年代被沃尔夫勒姆证明具有计算普适性。这意味着该自动机的行为可以实现任意计算（等价于一台图灵机）。在实际演示中，规则110利用特定的静态背景和移动“粒子”来模拟与门或逻辑门。这一发现表明，元胞自动机可以作为一种计算平台，只需极其简单的规则即可实现通用计算。
3.1.3 规则90：谢尔宾斯基三角
规则90（二进制01011010）从单细胞初始条件出发，产生一个漂亮的谢尔宾斯基三角形（西尔平斯基地毯图案）。每一代生成的分形结构完美复现了帕斯卡三角形模2的图案。规则90是理解元胞自动机如何通过线性规则（异或操作）生成自相似几何的经典范例。
3.2 二维元胞自动机
3.2.1 康威生命游戏
3.2.1.1 静止结构与振荡器
生命游戏中存在大量稳定构型，称为“静止结构”。最常见的是“方块”和“蜂巢”；它们永远不会变化。振荡器是一种周期结构，在有限步骤后恢复到与初始相同的形状。最简单的振荡器是“闪光灯”（周期8，在水平与竖直间交替闪烁），其他著名振荡器包括“蛙”、“脉冲星”等。
3.2.1.2 滑翔机与飞船
滑翔机是生命游戏中最著名的移动结构，其形状像一只飞行的鸟，每4步沿对角线移动一格，周期4。另一类移动结构称为“飞船”，可沿水平或竖直方向移动，例如“轻量级飞船”（LWSS）、“中量级飞船”（MWSS）和“重量级飞船”（HWSS）。这些移动结构可以通过相互碰撞产生新的结构，是生命游戏构建可编程逻辑阵列的基础。
3.2.1.3 通用图灵机实现
2010年，研究人员使用生命游戏中的复杂结构（如“戈斯珀滑翔机枪”和“斯普林格”等）成功构建了一台通用图灵机。这台图灵机由成千上万个稳定模块和滑翔机流组成，能够在需要时读取、写入、删除和移动数据，证明了生命游戏本身具有计算普适性。
3.2.2 其他二维规则（如“HighLife”、“Brain”）
- HighLife：修改生命游戏的存活规则为23/36，新增了“6邻域”复活条件。HighLife最著名的能力是能自发生成一种名为“繁殖者”的移动结构，该结构在蔓延的同时留下稳定种群。
- Brain：一种支持不同状态（静止、兴奋、不应期）的自动机，用于模拟神经元的“点火-不应期”行为。Brain规则能产生螺旋波和信号扩散模式，是计算神经科学的概念模型。
3.3 三维与更高维
3.3.1 3D生命游戏（如“B3/S23”变种）
将生命游戏规则推广到三维立方体网格，典型规则如“B3/S23”（类似生命游戏，但邻居计数包括面邻接和体对角）。三维自动机可以被观看为三维数据结构，或投影到二维视频。著名的三维自动机如“Spirogerm”能产生更复杂的自复制结构。
3.3.2 超立方体上的尝试
理论上，元胞自动机可以定义在任意高维环面上。超立方体上的自动机因邻居数量极多（如4维中，邻域半径1时邻居数为8+8=16）而难以直观分析。此类研究多聚焦于统计学性质，如临界相变模拟。
3.4 沃尔夫勒姆分类
3.4.1 第1类：稳定态
所有元胞几乎立即收敛到均匀状态（全0或全1），或少数稳定斑块。第1类自动机对应热力学平衡态。常见示例：规则0（全0）、规则255（全1）。
3.4.2 第2类：周期态
系统演化到由少数重复的周期结构组成的稳定图案（如条纹或斑马线）。规则4（“铁路”）产生向左或向右移动的重复条纹。
3.4.3 第3类：混沌态
从初始条件起，系统就产生持续变化的随机图案，时间演化无法预测。规则30是典型。第3类自动机对应于经典混沌动力学。
3.4.4 第4类：复杂态（边缘混沌）
第4类自动机位于有序与混沌之间，包含长寿命的相互作用结构、移动突触和各种混沌与有序区域的交界。规则110和生命游戏均为第4类。第4类系统被认为是计算普适性所在的相区，也是复杂系统科学最关注的对象。
4.1 物理模拟
4.1.1 流体动力学与晶格气动
基于元胞自动机可以构建“晶格玻尔兹曼方法”的前驱——晶格气动模型。这种模型将流体粒子抽象为在网格上沿特定方向运动的元胞，通过碰撞和迁移规则模拟宏观Navier-Stokes方程。典型的“HPP模型”在2D六边形网格上运行，而“FHP模型”则采用正六边形格点。晶格方法在微尺度流动和多孔介质模拟中仍有应用。
4.1.2 反应-扩散系统（如BZ反应）
基于二维元胞自动机可以模拟别洛乌索夫-扎鲍京斯基（BZ）振荡化学反应。使用多状态（如三种或更多状态）的自动机，其中一种状态对应于反应物浓度，可以产生可见的螺旋波、靶波和同心圆环图案，与真实化学实验相符。这种模拟帮助化学家理解空间自组织过程。
4.2 生物与生态建模
4.2.1 细胞分化与形态发生
元胞自动机可模拟胚胎发育中的形态发生过程，用状态集表示不同类型的细胞，规则控制细胞增殖、迁移、特化。例如模拟叶序(phyllotaxis)或动物皮毛斑纹（豹斑、斑马纹）。生命游戏中被观察到用于建造复杂结构的分化控制，为合成生物学提供了概念灵感。
4.2.2 种群动态与森林火灾
生态学中，元胞自动机常用于建模种群扩散和竞争：将每个元胞视为“生境块”，状态表示有无物种占据，规则模拟迁移、繁殖和灭绝。经典的“森林火灾”模型假设树木、微火种和灰烬三种状态，能够再现火灾蔓延的临界密度。
4.3 密码学与伪随机数生成
规则30的速度快、输出伪随机性强，简单实现即能产生高质量随机序列。其随机性通过测试表明，可用于流密码或随机数生成器。较复杂的元胞自动机如二维生命游戏的状态，也可用于扩大密钥空间或增强伪随机行为。
4.4 并行计算与可重构硬件
元胞自动机天然为细粒度并行计算模型。在FPGA（现场可编程门阵列）中，可以构建专用硬件加速器，以几纳秒为周期完成全局更新。这类加速器常用于实时仿真（如液体、火焰特效）或特殊函数计算。一些研究人员尝试将大规模元胞自动机用作可重构计算资源——将运算问题编码为初始图案，让自动机同步计算出结果（“自动机计算”）。
4.5 元胞自动机与机器学习
4.5.1 元胞神经网络
元胞神经网络（Cellular Neural Network, CNN，也常称作CNN/ANN的混合体）将每个元胞设计成一个非线性动态单元，神经元间通过局部连接规则相互作用。这种结构在处理图像处理、模板匹配等空间任务时具备实时能力。
4.5.2 演化规则与遗传算法
利用进化算法优化元胞自动机的规则，是“人工生命”领域中常见的方法。典型的设定是：随机初始化一组规则，以某个目标（如产生最大的自组织模式、计算帕斯卡三角、模拟特定函数）作为适应度函数，然后交叉、变异，迭代筛选出最优规则。演化出的自动机往往能完成难以手工设计的任务。
5.1 生命游戏中的“梗”与彩蛋
5.1.1 “Golly”软件与超级模式
Golly是最流行的生命游戏模拟器，支持无限网格和超大尺寸图案。它内置了“Patterns”和“Examples”库，包含了许多由爱好者发现的超级模式，例如“戈斯珀滑翔机枪”（Glider Gun）、“麦比乌斯环”、“通用计算机”。在日常圈子里，生命游戏爱好者会共享“低速结构竞赛”和“最小周期搜索”等趣味挑战。著名的“死亡之星”图案可以在网格中“压制”其他结构，而许多新模式（如“Simkin滑翔机枪”）会以幽默名称流传。
5.1.2 自复制“生命”的哲学隐喻
生命游戏常被用来讨论“生命”的定义。虽然本质上只是计算机中的像素跳动，但自我繁殖、自组织结构的存在，令观众感到它接近某种“人工生命”。哲学上，生命游戏引发了对涌现、决定论、朴素唯物主义等问题的讨论：是否复杂规律一定需要复杂的设计？局部决定论怎么与宏观目的性共存？这类思考常出现在同人创作和网络段子中。
5.2 元胞自动机在艺术与音乐中的应用
5.2.1 生成艺术与像素画
许多数字艺术家利用元胞自动机生成抽象动画或静态图案。例如，将一维规则90在二维卷曲投射下生成谢尔宾斯基花纹，或利用生命游戏生成随机迷宫、树根、细胞分裂。这些图案可用于T恤设计、壁纸或特效。一些著名画作如《自动生长》就源自二维元胞自动机的结果。
5.2.2 音序器与算法作曲
将一维元胞自动机的更新序列转换为音高、节拍或MIDI指令，可以创作出独特的电子音乐。有些软件内置了以规则30或规则110作为音序源的模块。电子音乐人中，尝试用生命游戏生成的“滑翔机”作为运动音符，创造出不断演进的旋律。随机规则也能模拟“即兴演奏”效果，被用于试验性音乐。
5.3 在流行文化中的出镜（如电影、游戏彩蛋）
- 电影《星际穿越》：黑洞“卡冈图雅”的吸积盘渲染中，部分粒子系统引用了元胞自动机思想来模拟混乱运动。
- 游戏《Minecraft》：玩家社区利用游戏内的红石电路构建了“生命游戏”计算机，以及可执行复杂逻辑的“自动机模拟器”。这些作品常在YouTube和Reddit上走红。
- 动画《瑞克和莫蒂》：某一集中主角创造了一个完整的文明，其中包含类似生命游戏的设计。
- 游戏《Watch Dogs》：黑客界面里经常出现动态生成的规则30图案，增添科技感。
- 其他：在许多科学馆或艺术展现场，元胞自动机被用来生成大型墙面投影或动态灯光装置。所谓“像素喷泉”等等，均可以追溯到这一模型的抽象美学。