元胞自动机

元胞自动机（pl.cellularautomata，缩写为CA）是在自动机理论中研究的离散计算模型。元胞自动机也称为元胞空间、曲面细分自动机、同构结构、元胞结构、曲面细分结构和迭代阵列。元胞自动机在各个领域都有应用，包括物理学、理论生物学和微观结构建模。

元胞自动机由规则的元胞网格组成，每个元胞都处于有限数量的状态之一，例如开和关（与耦合地图格子相反）。网格可以是任意有限维数。对于每个像元，相对于指定像元定义一组称为其邻域的像元。通过为每个单元分配一个状态来选择初始状态（时间t=0）。根据一些固定规则（通常是数学函数），创建新的一代（t增加1）它根据单元格的当前状态及其附近单元格的状态确定每个单元格的新状态。通常，更新单元格状态的规则对于每个单元格都是相同的，不会随时间变化，并且同时应用于整个网格，尽管已知例外，例如随机元胞自动机和异步元胞自动机.

这个概念最初是由斯坦尼斯拉夫·乌拉姆和约翰·冯·诺依曼在1940年代发现的，当时他们在洛斯阿拉莫斯国家实验室工作。虽然在1950年代和1960年代被一些人研究，但直到1970年代和康威的生命游戏，二维细胞自动机，对该主题的兴趣才扩展到学术界之外。1980年代，StephenWolfram对一维元胞自动机或他所谓的基本元胞自动机进行了系统的研究；他的研究助理MatthewCook表明，这些规则之一是图灵完备的。Wolfram发表2002年的ANewKindofScience，声称元胞自动机在许多科学领域都有应用。这些包括计算机处理器和密码学。

Wolfram概述的元胞自动机的主要分类编号为一到四。它们依次是模式通常稳定为同质性的自动机，模式演变成大部分稳定或振荡结构的自动机，模式以看似混乱的方式演变的自动机，以及模式变得极其复杂并可能持续一段时间的自动机。很长一段时间，具有稳定的局部结构。最后一类被认为是计算通用的，或者能够模拟图灵机。

模拟二维​​元胞自动机的一种方法是使用一张无限大的方格纸以及一组细胞要遵循的规则。每个方块称为一个“单元格”，每个单元格都有两种可能的状态，黑色和白色。单元格的邻域是附近的，通常是相邻的单元格。两种最常见的邻域类型是冯诺依曼邻域和摩尔邻域。前者以元胞自动机理论创始人的名字命名，由四个正交相邻的元胞组成。后者包括冯诺依曼邻域以及四个对角相邻的单元格。对于这样的单元格及其摩尔邻域，有512(=29)种可能的模式。对于512个可能的模式中的每一个，规则表将说明中心单元格在下一个时间间隔是黑色还是白色。Conway'sGameofLife是该模型的流行版本。另一种常见的邻域类型是扩展的冯诺依曼邻域，它包括每个正交方向上两个最近的像元，总共八个。这种规则系统的一般方程是kks，其中k是单元格的可能状态数，而s是用于确定单元格下一状态的相邻单元格（包括要计算的单元格本身）的数量。因此，在具有摩尔邻域的二维系统中，可能的自动机总数为229，或1.34×10154。

通常假设宇宙中的每个细胞都以相同的状态开始，除了有限数量的处于其他状态的细胞；状态值的分配称为配置。更一般地说，有时假设宇宙开始时被一种周期性模式覆盖，只有有限数量的细胞违反了这种模式。后一种假设在一维元胞自动机中很常见。

Wolfram在ANewKindofScience和1980年代中期的几篇论文中定义了四类，元胞自动机和其他几个简单的计算模型可以根据它们的行为分为四类。虽然早期的元胞自动机研究倾向于尝试识别特定规则的模式类型，但Wolfram的分类是对规则本身进行分类的xxx次尝试。按照复杂性的顺序，这些类是：

• 第1类：几乎所有初始模式都迅速演变为稳定、同质的状态。初始模式中的任何随机性都会消失。
• 第2类：几乎所有初始模式都会迅速演变为稳定或振荡的结构。初始模式中的一些随机性可能会被过滤掉，但一些仍然存在。初始模式的局部变化往往保持局部。
• 第3类：几乎所有初始模式都以伪随机或混沌方式演化。任何出现的稳定结构都会被周围的噪音迅速破坏。初始模式的局部变化往往会无限扩散。
• 第4类：几乎所有初始模式都演变成以复杂而有趣的方式相互作用的结构，形成能够长期存活的局部结构。2类稳定或振荡结构可能是最终结果，但达到这种状态所需的步骤数量可能非常大，即使初始模式相对简单。初始模式的局部变化可能会无限扩散。Wolfram推测许多第4类元胞自动机（如果不是全部）都能够进行通用计算。规则110和康威的生命游戏已经证明了这一点。

这些定义本质上是定性的，有一些解释的空间。根据Wolfram的说法，“……对于几乎任何一般分类方案，都不可避免地存在根据一个定义分配给一个类而根据另一个定义分配给另一个类的情况。元胞自动机也是如此：偶尔有规则……显示一个类的一些特征和另一个类的一些特征。”Wolfram的分类根据经验与元胞自动机输出的压缩长度的聚类相匹配。

受到Wolfram分类的启发，已经有几次尝试将元胞自动机分类为形式严格的类。例如，Culik和Yu提出了三个明确定义的类（第四个类用于与这些中的任何一个都不匹配的自动机），它们有时被称为Culik-Yu类；事实证明，这些成员的身份无法确定。Wolfram的第2类可以分为稳定（定点）和振荡（周期）规则的两个子组。

有4类动力系统的想法最初来自诺贝尔奖获得者化学家IlyaPrigogine，他确定了这4类热动力系统-(1)热力学平衡系统，(2)空间/时间均匀系统，(3)混沌系统，以及(4)具有耗散结构的远离平衡的复杂系统（参见Nicolis论文中的图1（Prigogine的学生））。

如果对于元胞自动机的每个当前配置，都只有一个过去的配置（原像），那么元胞自动机是可逆的。如果将元胞自动机视为将配置映射到配置的函数，则可逆性意味着该函数是双射的。如果元胞自动机是可逆的，那么它的时间反转行为也可以描述为元胞自动机；这一事实是Curtis-Hedlund-Lyndon定理的结果，该定理是元胞自动机的拓扑特征。对于并非每个配置都有原像的元胞自动机，没有原像的配置称为伊甸园模式。

对于一维元胞自动机，存在用于确定规则是可逆还是不可逆的已知算法。然而，对于二维或多维元胞自动机，可逆性是不可判定的；也就是说，不存在将自动机规则作为输入并保证正确确定自动机是否可逆的算法。JarkkoKari的证明与王瓦的平铺问题有关。

可逆元胞自动机通常用于模拟气体和流体动力学等物理现象，因为它们遵守热力学定律。这种元胞自动机具有专门构造为可逆的规则。TommasoToffoli、NormanMargolus和其他人已经研究过这样的系统。有几种技术可用于显式构建具有已知逆元的可逆元胞自动机。两种常见的是二阶元胞自动机和块元胞自动机，两者都涉及以某种方式修改元胞自动机的定义。虽然这样的自动机不严格满足上面给出的定义，但可以证明它们可以被具有足够大的邻域和状态数量的传统元胞自动机模拟，因此可以被认为是传统元胞自动机的子集。相反，已经表明每个可逆元胞自动机都可以由块元胞自动机模拟。

一种方法是使用矩形（立方体等）网格以外的其他东西。例如，如果平面平铺有规则六边形，这些六边形可以用作单元格。在许多情况下，生成的元胞自动机等效于具有特殊设计的邻域和规则的矩形网格的元胞自动机。另一种变化是使网格本身不规则，例如Penrose瓷砖。

此外，规则可以是概率性的，而不是确定性的。这种元胞自动机称为概率元胞自动机。对于时间t的每个模式，概率规则给出了中央单元在时间t+1转换到每个可能状态的概率。有时使用更简单的规则；例如：“规则是生命游戏，但在每个时间步上，每个单元格有0.001%的概率会转换为相反的颜色。”

邻里或规则可能会随着时间或空间而改变。例如，最初单元格的新状态可以由水平相邻的单元格确定，但对于下一代，将使用垂直单元格。

在元胞自动机中，一个元胞的新状态不受其他元胞的新状态影响。这可以改变，例如，一个2x2的单元格可以由它自己和与其相邻的单元格确定。

连续空间自动机具有连续的位置。位置的状态是有限数量的实数。时间也是连续的，状态按照微分方程演化。一个重要的例子是反应扩散纹理，这是艾伦图灵提出的微分方程，用于解释化学反应如何在斑马上产生条纹和豹子上的斑点。当这些被元胞自动机逼近时，它们通常会产生相似的模式。MacLennan将连续空间自动机视为计算模型。

有一些已知的连续空间自动机的例子，它们表现出类似于生命游戏中的滑翔机的传播现象。

图重写自动机是基于图重写系统的元胞自动机的扩展。

组合自动机功能通过检查奇数/偶数索引对是否等于排列X。如果是，则返回规则字符串的X（例如：“120012101”）。这些CA与砖墙社区合作。这些CA类型也像逻辑门一样。例如，当初始状态是单个居中单元时，组合中XOR门的等效项会生成谢尔宾斯基三角形。

最简单的非平凡元胞自动机是一维的，每个元胞有两种可能的状态，元胞的邻居定义为它两侧的相邻元胞。一个单元和它的两个邻居形成了一个由3个单元组成的邻域，因此一个邻域有23=8种可能的模式。规则包括为每个模式决定单元格在下一代中是1还是0。那么有28=256条可能的规则。

一维元胞自动机的规则决定下一代的方式的动画。

这256个元胞自动机一般用它们的Wolfram代码来指代，这是Wolfram发明的一种标准命名约定，它为每个规则赋予一个从0到255的数字。多篇论文对这256个元胞自动机进行了分析和比较。在第30条和第110元胞自动机是特别有趣。下图显示了当起始配置由1（在每个图像的顶部）和0包围时的历史记录。每一行像素代表自动机历史中的一代，t=0是最上面一行。每个像素为0为白色，1为黑色。