用于元胞自动机中粒子流动模拟的条件性交通规则类方法

《Chaos, Solitons & Fractals》：Conditional traffic-like rules for particle-flow simulation in cellular automata

　　•本文介绍了一种独特的模块化表示方法，用于表示保持数字的元胞自动机。每个自动机由一对（Ω,Λ）描述，这对参数控制全局和局部运动。所提出的框架能够追踪单个粒子的轨迹。所有具有2×3邻域的二进制保持数字的自动机都得到了表征。这种方法为设计和分析Moore邻域规则提供了新的工具。

引言
由于元胞自动机（CAs）能够使用简单的局部规则来表示复杂系统，因此它们被广泛用于模拟各种自然现象（参见Osmanovi?和Franco [1]；Brown和Sneppen [2]；Nessi [3]；Noureen等人[4]的最新应用）。特别是，几十年来，它们被用于模拟各种物理系统，尤其是在需要考虑不同守恒定律的情况下[5]、[6]、[7]。关于CAs作为物理系统的离散模型的经典描述及其早期应用的概述可以在Toffoli和Margolus [8]中找到。其中一个例子是一组移动的粒子。在典型的场景中，通常假设这些粒子是不可区分的，并且在假设的d维规则网格中移动，同时它们的数量是恒定的（即，粒子不能凭空出现或消失）。还经常假设在任何时间点每个单元格中最多只能有一个粒子（如有必要，可以减小单元格的大小）。在CA建模中，这些假设的结合导致了所谓的保持数字的二进制CA。

在设计一个模拟给定现象的保持数字的二进制CA时，首先提取粒子的非常局部的行为，然后将其转化为所创建CA的局部规则语言。这一过程最简单且最著名的例子是所谓的交通规则。这里，我们从一个一维的单元格网格开始，每个粒子向一个固定的方向（例如向右）移动，但前提是它前面的单元格是空的。这种行为足以构建一个具有半径为一的非常简单的局部规则的CA，可以用以下表格形式表示，称为LUT（查找表）。

如今，由于计算机可以使用LUT生成大量的CA（例如，使用先进的遗传算法），一个自然而然的问题出现了：相反的过程是否可行？也就是说，给定一个保持数字的二进制CA，我们能否用粒子位移表示法来描述它？事实证明，这项任务通常并不容易。首先应该指出，对于给定的二进制CA，可以根据其LUT来检查它是否保持数字。从数学上讲，这归结为检查一组线性方程（参见例如[9]），因此并不复杂，可以很容易地交给计算机来完成。最后一点是关键的，因为对于具有m大小邻域的二进制局部规则，LUT的列数等于2^m。例如，考虑一个具有Moore邻域（由9个单元格组成）的二维二进制CA，我们会得到一个包含多达512个值的LUT。仅凭这512个LUT值，很难看出，因此也很难理解给定CA的动力学行为。我们最渴望的是使用某种算法，并借助计算机的帮助，回答给定CA是否具有我们感兴趣的某些属性的问题。不幸的是，大多数受物理现象启发的属性都是不可判定的（通常在维度大于一的情况下[10]、[11]）。例如，可逆性就是一个这样的例子：一般来说，没有算法可以确定给定的二维CA是单射还是满射[12]。然而，人们相信，对于由保持数字的CA组成的子类，许多不可判定的属性可能是可判定的。因此，将给定保持数字的二进制CA的LUT转化为粒子运动表示，使我们有机会“在微观层面上”理解这种CA的工作原理，并从新的角度分析它。

对于一维保持数字的CA，可以说将给定的CA转化为粒子位移表示的任务已经得到了很好的研究（不仅仅针对二进制状态集）。已经证明，每个一维保持数字的CA都可以使用运动表示来解释；此外，任何这样的CA都可以通过某种规范的运动表示形式唯一地表征（详情参见Boccara和Fuk?、Pivato、Fuk?、Moreira等人[13]、[14]、[15]、[16]、[17]）。通过使用流函数，还实现了一维保持数字的CA的另一种非常有趣的表征方法，这些流函数描述了根据边界邻域的不同，有多少粒子穿过两个相邻单元格之间的边界[18]。

在二维情况下，运动表示的主题尚未得到充分探索，尽管也已经显示任何二维保持数字的CA的动力学都可以用粒子位移来表达[19]。然而，对于这样的CA，通常有无限多的运动表示方式，很难定义一个“规范”的表示方法。在可逆计算的背景下，也较早研究了非平凡的二维保持数字的元胞自动机。特别是Morita等人[20]构建了能够进行通用计算的可逆和保持数字的二维元胞自动机，在这些自动机中，计算是通过适当控制的粒子的运动和相互作用来实现的。

当涉及到更高维度时，关于保持数字的CA的运动表示几乎没有结果，即使在二进制情况下也是如此。尽管Kari和Taati [19]的结果可以推广到三维或更多维度，但在这个方向上的研究并没有继续进行。

一个重要的例外是具有von Neumann邻域的保持数字的CA，对于这类CA已经知道了一些结构结果。Tanimoto和Imai [21]推导出了二维von Neumann邻居CA保持数字的必要和充分条件，无论是否具有旋转对称性，并为旋转对称情况得到了一种构建方法。Tanimoto等人[22]进一步研究了具有von Neumann邻域的旋转对称保持数字的CA的额外限制，特别是关于所需状态数量的限制。

对于具有von Neumann邻域的保持数字的CA，首先有一种用垂直、水平和 diagonal方向的流函数来表征这类CA的方法[21]（但同样的问题再次出现：流函数不是唯一定义的）。然而，如果我们仅关注二进制情况，那么使用另一种数学工具——分裂-扰动分解[23]（专门为研究具有von Neumann邻域的d维保持数字的CA而设计），我们可以轻松找到所有这样的二进制CA。结果发现，这类CA只有4d+1种：恒等规则、每种2d方向上的移位规则和交通规则[24]。通过这种方式，具有von Neumann邻域的d维保持数字的二进制CA的结构被完全揭示：无论维度d如何，所有这些CA都是平凡的，因为它们本质上一维的，这使得我们可以详细描述这些自动机的运动表示[24]。这一结果归因于von Neumann邻域的几何特性（详见Wolnik等人[23]）。不幸的是，这种方法在Moore邻域的情况下是不可行的。即使对于d=2，具有此类邻域的所有二进制CA的集合的基数也达到了惊人的2^512，目前还没有人能够回答其中有多少是保持数字的，以及它们的动力学行为是什么（使用上述必要和充分条件[9]超出了计算机的计算能力）。

尽管如此，仍然提出了几种构建具有更大邻域的二维保持数字的CA的方法。Tanimoto和Imai [25]建立了一个Moore邻域CA保持数字的充分条件。在这个框架内，旋转对称保持数字的CA的局部函数可以表示为更简单函数的总和，作者利用这种表示方法构建了一个六态的逻辑通用保持数字的CA。另一个方法可以在Ishizaka等人[26]中找到，其中提出了一种算法，可以生成定义在n×m邻域上的所有二维“可运动表示”的保持数字的二进制CA。结果表明，在2×2和2×3的情况下，这种算法可以有效搜索所有保持数字的二进制CA。然而，由于其复杂性，这种方法从未在d=2的Moore邻域情况下使用过，更不用说更大的情况了。

在本文中，我们提出了一种将保持数字的二进制CA视为“模块化规律”来控制粒子运动的全新视角。在这种新的见解中，每个这样的规律由两部分组成：一部分是对整个系统在指定方向Ω上的整体运动的总体規制，另一部分是一组在局部应用的规制Λ。将CA表示为一对（Ω,Λ）有以下优点。首先，这两部分都是唯一确定的。其次，我们得到的是一个简短的、透明的解释，而不是长篇的数学描述（以LUT的形式）。此外，这种表示方法允许我们像在本文后面看到的那样，分别跟踪每个粒子的运动。这使得理解所研究CA的动力学以及验证其属性（例如可逆性）变得更加容易。

事实证明，我们的方法使得描述具有von Neumann邻域和2×3邻域的所有二维保持数字的二进制CA变得容易。目前还不知道这种方法是否也能描述所有具有Moore邻域的二维保持数字的二进制CA。然而，它已经是一个非常有用的工具，用于设计高度非平凡的此类CA并研究它们的属性。

本文的其余部分组织如下。第2节介绍了关键定义和新方法的描述。第3节使用所提出的方法找到了所有具有2×3邻域的二维保持数字的二进制CA并描述了它们的动力学。第4节包含了在Moore邻域情况下应用所介绍方法的示例。第5节报告了结论和未来的工作。

### 细节
#### 具有半径为一的元胞自动机模拟粒子流动
在本文中，我们假设所考虑的元胞空间C是无限的，对应于整个空间Zd，其中d是一个正整数。然而，这些结果也适用于任何有限的元胞空间，该空间对应于大小为N=(n1,n2,...,nd)的d维长方体，并具有周期性边界条件，即C=CN=Z^n1×Z^n2×...×Z^(nd-1)，其中n1,n2,...,nd>2。我们使用Q={0,1}作为状态集，其中状态1被解释为一个粒子。

#### 具有2×3邻域的二维保持数字的二进制CA
在本节中，我们引入了交通规则的推广，并研究了当两个这样的规则在不同方向上作用时，它们是否可以在同一个元胞自动机中共存。我们将这种在单个CA中同时存在多个控制粒子运动的局部交通的现象称为这些交通的“混合”。当不存在这些交通会导致粒子运动冲突的局部配置时，两种（或更多种）交通的混合是可能的。由于我们将展示，2×...

#### 二维Moore邻域的情况
上一节中使用的方法可以很容易地推广到任何半径为一的d维邻域的情况，在本节中，我们将展示如何将其应用于二维Moore邻域。首先，可以利用这种邻域结构来设计具有非平凡数保持特性的二进制细胞自动机（Cell Automata，简称CA）。当然，我们可以从摩尔（Moore）邻域包含2×3邻域这一事实出发，因此前一节中描述的74条规则可以直接应用。

**结论与未来工作**
在本文中，我们提出了一种创新的方法来描述半径为1的二维二进制CA的结构，这些CA可以模拟粒子流动。通过提供一种简单明了的物理解释（即粒子运动规则类似于交通规则），我们对这些动态系统有了全新的认识。该方法中使用的条件性交通规则可以直观地理解为依赖于局部环境条件的粒子流动——类似于汽车的行驶行为。

**作者贡献声明**
Barbara Wolnik：负责写作、审稿与编辑工作，以及原始稿件的撰写；方法论研究及概念化。
Dominik Micha? Falkiewicz：负责原始稿件的撰写；软件开发及方法论研究。
Witold Bo?t：负责方法论研究。
Adam Rutkowski：负责原始稿件的撰写及指导工作。
Bernard De Baets：负责审稿与编辑工作；方法论研究。

**利益冲突声明**
作者声明：他们没有已知的财务利益冲突或个人关系，这些因素可能会对本文所述的工作产生影响。

作者列表：
Barbara Wolnik | Dominik Micha? Falkiewicz | Witold Bo?t | Adam Rutkowski | Bernard De Baets