全局检索与知识浏览

斯蒂芬·沃尔弗拉姆（Stephen Wolfram）在其2003年开创性著作《一种新科学》（A New Kind of Science）中宣称，以细胞自动机（Cellular Automata, CA）形式存在的简单递归程序，有望取代当前广泛使用的数学形式化方法（如微分方程），从而提升对复杂系统的建模能力。二十多年后，尽管细胞自动机在科学应用中仍未取得实质性突破，近期研究却展现出将沃尔弗拉姆思想与可学习的人工神经网络相结合的新路径：所谓神经元细胞自动机（Neural Cellular Automata, NCA）能够从数据样本中学习CA复杂的更新规则，从而建模具有自组织特性的复杂生成系统。本文旨在综述现有NCA相关工作，并提供统一的模块化框架与符号体系，以及基于开源库NCAtorch的参考实现。补充材料、视频及代码详见项目网站：https://www.neural-cellular-automata.org/

斯蒂芬·沃尔弗拉姆（Stephen Wolfram）在其2003年开创性著作《一种新科学》（A New Kind Of Science）中宣称，以细胞自动机（Cellular Automata, CA）形式存在的简单递归程序，有望取代当前广泛使用的数学形式化方法（如微分方程），从而提升对复杂系统的建模能力。二十多年后，尽管细胞自动机在科学应用中仍未取得实质性突破，近期研究却展现出将沃尔弗拉姆思想与可学习的人工神经网络（Artificial Neural Networks）相结合的新路径：所谓神经元细胞自动机（Neural Cellular Automata, NCA）能够从数据样本中学习CA的复杂更新规则，从而建模具有自组织特性的复杂生成系统。本文旨在综述现有NCA相关工作，并提供一套统一的模块化框架与符号体系，以及基于开源库NCAtorch的参考实现。

本文研究一维及二维细胞自动机（CA）的归纳推断问题，即根据有限数量的可用数据推断出一个与之兼容的CA。此处的数据以有限个区间的形式给出，每个区间由状态集字母表上的两个字w和w'以及一个正整数i组成。推断目标是构造一个CA，使其对每个区间(w, w', i)均兼容，即该CA能在i步内由w导出w'。我们考虑该问题的三种变体：1）CA完全预先已知，目标为验证其兼容性；2）CA部分预先已知，目标为将其扩展为一个完整的、兼容的CA；3）CA完全未知，目标为在存在解的前提下完整构造一个兼容的CA。对于全部三种变体，推断均可在多项式时间内完成，且该问题属于P-完全问题。

元胞自动机（CA）是在格点上按局部更新规则演化的离散时间动力系统。尽管其定义极为简单，CA 却能展现出统计物理中一系列核心的宏观现象：平衡态与非平衡态相变、输运行为与流体力学极限、动力学粗糙化、自组织临界性，以及复杂的时空关联。本综述聚焦于三个紧密关联的主题：（i）将 CA 视为构型空间上的平移交换映射，从结构角度进行刻画，重点讨论规则复杂性、可逆性及守恒律（包括离散连续性方程）；（ii）将 CA 中的输运行为划分为弹道型、扩散型与反常型三类，并通过 Green–Kubo 公式、标度理论及普适性类，将微观流与宏观定律相联系；（iii）发展基于关联的方法——涵盖结构因子与响应公式、计算力学及数据驱动推断——以诊断不同物态并实现粗粒化建模。

元胞自动机（CA）是一类定义在格点上的离散时间动力系统，其演化由局部更新规则决定。尽管定义简单，CA 却能展现出统计物理中诸多核心的宏观现象：平衡态与非平衡态相变、输运行为与流体力学极限、动力学粗糙化、自组织临界性，以及复杂的时空关联。本综述聚焦于三个紧密关联的主题：（i）将 CA 视为构型空间上平移交换映射，从结构角度进行刻画，重点讨论规则复杂性、可逆性及守恒律（包括离散连续性方程）；（ii）将 CA 中的输运行为划分为弹道型、扩散型与反常型三类，并通过 Green–Kubo 公式、标度理论及普适性类，将微观流与宏观定律相联系；（iii）发展基于关联的方法——涵盖结构因子与响应公式、计算力学及数据驱动推断——以识别不同物态并实现粗粒化描述。

我们研究一类一维二值概率元胞自动机（PCA），其在Wolfram经典规则23、77、178和232之间进行插值。这些规则是唯一满足以下两个条件的规则：（i）当邻域状态存在多数时，中心格点取多数状态或其相反状态；（ii）当邻域状态平局时，中心格点改变其当前状态或保持不变。该PCA由两个参数为 $p,r \in [0,1]$ 的Bernoulli随机变量定义；我们通过马尔可夫过程建模，解析求解小规模情形。我们推导出所有初始状态下，系统渐近达到每一可能全局构型的概率关于 $p$ 和 $r$ 的解析表达式。我们证明：当 $0 < p,r < 1$ 时，该PCA达到任一状态的渐近概率分布与初始条件无关。这与确定性Wolfram规则23（$p=0,r=0$）、77（$p=1,r=0$）、178（$p=0,r=1$）和232（$p=1,r=1$）的行为形成对比——后者的渐近行为中可能出现额外状态，特别是周期性构型。最后，我们讨论将此类PCA应用于描述含犹豫代理者的意见动力学。

我们研究一类一维二值概率元胞自动机（PCA），其在Wolfram经典规则23、77、178与232之间进行插值。这些规则是唯一满足以下两个条件的规则：（i）当邻域状态存在多数时，中心格点取多数状态或其相反状态；（ii）当邻域状态平局时，中心格点改变其当前状态或保持不变。该PCA由两个参数为 $p,r \in [0,1]$ 的Bernoulli随机变量定义；我们通过马尔可夫过程建模，对小规模情形进行解析求解。我们推导出所有初始状态下，系统渐近达到每一可能全局构型的概率关于 $p$ 和 $r$ 的解析表达式。我们证明：当 $0 < p,r < 1$ 时，PCA达到任一全局构型的渐近概率分布与初始条件无关。这与确定性Wolfram规则23（$p=0,r=0$）、77（$p=1,r=0$）、178（$p=0,r=1$）及232（$p=1,r=1$）的行为形成对比——后者的渐近行为中可能出现额外状态，特别是周期性构型。最后，我们讨论将此类PCA应用于描述涉及犹豫型主体的意见动力学。

我们研究一类一维二值概率元胞自动机（PCA），其在Wolfram经典规则23、77、178和232之间进行插值。这些规则是唯一满足以下两个条件的规则：（i）当邻域状态存在多数时，中心格点取多数状态或其相反状态；（ii）当邻域状态平局时，中心格点改变其当前状态或保持不变。该PCA由两个参数为 $p,r \in [0,1]$ 的Bernoulli随机变量定义；我们通过马尔可夫过程建模，对小规模情形进行解析求解。我们推导出所有初始状态下，系统渐近达到每一可能全局构型的概率关于 $p$ 和 $r$ 的解析表达式。我们证明：当 $0 < p,r < 1$ 时，PCA达到任一全局状态的渐近概率分布与初始条件无关。这与确定性Wolfram规则23（$p=0,r=0$）、77（$p=1,r=0$）、178（$p=0,r=1$）和232（$p=1,r=1$）的行为形成对比——在这些确定性情形下，可能出现额外的渐近态，特别是周期性构型。

本文对至少存在一个不动点的初等元胞自动机（Elementary Cellular Automata）在顺序更新模式下的收敛性进行了理论分析。我们的目标是确定哪些初等规则在任意初始构型下，均能在顺序更新模式下最终达到不动点。在此框架下，我们依据这些规则在同步（或并行）更新模式下是否具有不动点，将其分类为：在所有、部分、某一种或无任何顺序更新模式下，所有初始构型均能收敛。

现有文献中定义的大多数神经元细胞自动机（NCA）均基于一个共同范式：采用规则网格结构及摩尔邻域（一跳邻居），未考虑大脑中存在的长程连接与更复杂的拓扑结构。本文提出BraiNCA——一种受脑启发的NCA，其引入注意力层、显式长程连接以及复杂拓扑结构。实验表明，在两项任务中，BraiNCA相较于标准NCA（Vanilla NCA）展现出更优的鲁棒性与更快的学习速度，证实了将基于注意力的消息选择机制与显式长程边相结合，可实现比纯局部、网格化更新规则更具样本效率且对损伤更具容忍性的自组织能力。这些结果支持如下假设：对于需在广阔时空尺度上实现分布式协同的任务，交互拓扑结构的选择以及动态信息路由能力将显著影响NCA的鲁棒性与学习速度。更广泛而言，BraiNCA提供了一种受脑启发的NCA建模框架，在保持去中心化局部更新原则的同时，更真实地反映非局部连接模式，因而成为研究生物现实网络结构下集体计算及演化认知基质的有力工具。

我们研究了概率性全总型元胞自动机的平均场表述逼近逻辑斯蒂方程的条件。结果表明，该目标仅在无限范围邻域下才能实现。我们数值研究了相应的二维一维实现，发现通过在每个时间步对配置进行随机重排，或以类似“小世界”机制的方式，在每个时间步重连部分连接，或仅一次性使用相同的随机采样进行重连，均可使平均场描述趋于成立。我们证明，即使重连连接的比例小于1，也能获得对逻辑斯蒂行为的良好近似。此外，我们还发现密度随重连比例变化呈现出分岔级联现象，且这一现象在具有与概率型元胞自动机相同基本对称性的确定性全总型元胞自动机中同样成立。

本文研究定义在环 $\mathbb{Z} / n \mathbb{Z}$ 上的均匀加权线性元胞自动机（LCA-UW）所生成的时空模式的分类问题。此类系统由状态规模 $n$ 和转移系数 $c$ 共同决定，二者耦合产生大量难以通过穷举观察加以系统归类的模式。我们引入一个二进制投影算子 $\mathcal{B}$，以聚焦于这些自动机的基本结构演化——即无限二进制轨道。我们的主要结果揭示了一条基本约化原理：对任意与 $n$ 具有公共素因子的系数 $c$，其所生成的无限二进制轨道最终将与某个具有约化后状态规模及单位系数 $c=1$ 的 LCA-UW 所生成的轨道重合。我们证明，对固定 $n$，恰好存在 $2^m - 1$ 种互异的二进制轨道类型，其中 $m$ 为 $n$ 的不同素因子个数。该定理实质上将二维参数空间 $(n, c)$ 约化为仅关于 $n$ 的一维搜索，从而为 LCA-UW 动力学的拓扑与分形分类提供了简明的框架。

计算能力可通过为计算装置赋予代数结构来度量。本文将康威生命游戏（Conway's Game of Life）的一个小区域转化为一个变换半群（transformation semigroup）。该转化不仅捕获时间演化，还涵盖交互操作，从而使该细胞自动机可直接编程。完成此度量后，我们对该所得代数对象应用分层分解，以增进对其理解。这些分解基于受统计力学启发的宏观/微观态划分。然而，细胞自动机具有大量全局状态，因此我们聚焦于状态空间的划分，并构建可作为宏观层次描述的同态像（morphic images）近似。本文所发展的方法不仅适用于细胞自动机，亦可推广至更一般的离散动力系统。

我们研究了一类由可加性初等规则60与102混合构成的概率元胞自动机。我们证明：对任意有限周期格点及混合参数 $λ=1/2$，该系统几乎必然在有限步内达到全零吸收态。此外，蒙特卡洛模拟还表明，在 $λ=1/2$ 附近的一个有限区间内亦存在零密度稳态。尽管系统呈现吸收行为，平均场理论与块近似方法均预测存在非零密度的稳态。这一失效源于确定性组分所具有的可加性与镜像对称性，凸显了有限块近似法在刻画概率元胞自动机全局动力学方面的一项根本局限性。

我们研究了采用多数表决或受挫多数表决规则、且相互作用范围可变的布尔型全同型细胞自动机。这两个模型的行为均偏离平均场行为。多数表决模型具有吸收态，其相变行为随初始密度变化，与平均场近似结果一致；但当初始密度为0.5时，系统动力学由粗化过程主导，该过程在形成具有确定曲率半径的团簇后停止。对于受挫多数表决模型，平均场近似预测混沌振荡或极限环，而我们实际观察到的是具有稳定密度的活性图案；当相互作用半径超过某一临界值时，渐近密度随初始密度变化出现分岔。

随着神经元细胞自动机（Neural Cellular Automata, NCAs）日益应用于人工生命领域之外的现实场景，深入理解其行为模式并构建恰当的解释路径变得尤为迫切。NCAs 的训练优势天然伴随着可解释性的缺失：我们能够设计出涌现行为，却难以理解其实际习得的内容。本文采用多种技术手段尝试打开 NCA 的‘黑箱’，以期获得对其学习内容的初步理解。我们结合流形学习技术（主成分分析、稠密与稀疏自编码器）及拓扑数据分析技术（持续同调），试图刻画 NCA 潜在的行为流形，效果各异。结果表明，在宏观尺度上（即以整个 NCA 状态作为一个数据点）进行分析时，其潜在流形通常较为简单，易于捕捉与分析；而在微观尺度上（即以单个细胞的状态作为一个数据点）进行分析时，该流形则高度复杂，需借助更复杂的技术方能有效解读。

均匀分布性（equidistribution）是一种理论质量指标，用于衡量线性伪随机数生成器（PRNG）的输出均匀性。本文首先指出，所有现有基于线性元胞自动机（CA）的伪随机数生成器在均匀分布性方面均表现较弱。随后，我们提出一系列轻量级组合式CA-based PRNG，采用时间间隔为 $2 \leq s \leq 10$ 的设计，并基于阶数为 $31 \leq k \leq 128$（接近计算机字长）的线性最大长度元胞自动机。我们证明，这些PRNG不仅达到最大周期，而且满足极大均匀分布性（maximal equidistribution property）。最后，我们验证这些组合式最大长度CA-based PRNG几乎通过全部经验测试套件，其运行速度与性能与梅森旋转算法（Mersenne Twister）相当。

我们研究定义在任意群宇宙 $G$ 与字母表 $A$ 上的最基础一类元胞自动机：懒惰元胞自动机（lazy cellular automata）。此类自动机在配置空间 $A^G$ 上作用为恒等映射，除非其读取到唯一的活跃转移模式 $p \in A^S$，此时它输出一个固定的符号 $a \in A$。如预期所料，懒惰元胞自动机的动力学行为相对简单，但由于其行为完全取决于 $p$ 与 $a$ 的选取，仍会产生微妙的问题。本文考察懒惰元胞自动机 $τ: A^G \to A^G$ 的阶，即集合 $\{ τ^k : k \in \mathbb{N} \}$ 的基数。特别地，我们基于 $p$ 的纤维（fibers）给出了 $τ$ 阶的一个通用上界，并证明当 $p$ 为拟常值模式（quasi-constant pattern）时该上界可达。

本文是一篇探索性研究，提出了认知智能体如何通过局部感知学习修改环境以达成全局目标的问题。我们聚焦于二维系统中的离散动力学（即元胞自动机）。结果表明：当环境为被动动力学时，智能体可学习逼近其目标；而当环境遵循主动动力学时，该任务则无法实现。

随着神经细胞自动机（Neural Cellular Automata, NCAs）在人工生命领域之外的玩具模型中日益得到应用，亟需深入理解其行为机制，并构建恰当的路径以解释其学习所得。本质上，训练NCAs所带来的优势与其可解释性的缺失形成权衡：我们能够设计出涌现行为，却难以理解其实际学到的内容。本文采用多种技术手段尝试打开NCA这一‘黑箱’，以期获得对其学习功能的初步理解。我们结合流形学习技术（主成分分析以及稠密与稀疏自编码器）和拓扑数据分析技术（持续同调），尝试刻画NCA潜在的行为流形，效果各异。结果表明，在宏观层面（即以整个NCA状态作为一个数据点）进行分析时，其潜在流形通常较为简单，可被较好地捕捉与分析；而在微观层面（即以单个细胞的状态作为一个数据点）进行分析时，该流形则高度复杂，需借助更复杂的技术方能加以解读。

针对有限和无限格点，已存在可在二次时间复杂度内检测元胞自动机（CA）可逆性的算法。然而，我们能否在常数时间内识别出一种 $d$-状态的CA规则，使其对任意格点尺寸 $n\in \mathbb{N}$ 均保持可逆？为解决此问题，本文研究了在零边界条件下，一类一维、三邻域、$d$-状态有限元胞自动机（CAs）——即一阶元胞自动机（FDCAs）——在任意细胞数 $n\in \mathbb{N}$ 下的可逆性特性。在一阶元胞自动机（FDCA）中，局部规则由八个参数定义。为确保 $d$-状态 FDCA 的全局转移函数对任意细胞数 $n\in \mathbb{N}$ 均可逆，只需验证参数值之间的三个代数条件即可。基于这些条件，对于任意给定的 $d$，均可合成所有可逆的 FDCAs 规则；同样地，对于给定的 FDCA 规则，可通过检查这三个条件在常数时间内判定其可逆性。

本文研究了时间非均匀细胞自动机（t-NUCAs），这是一种非均匀细胞自动机的变体，在其演化过程中按顺序使用两种规则。本文考虑了一维t-NUCAs在有限及无限格点上的情况。研究了t-NUCAs的满射性与单射性。同时探讨了t-NUCAs的可逆性。最后，对有限t-NUCAs的循环行为进行了分析。

经典细胞自动机是一类显式的离散时空格点模型，其复杂的大尺度现象源于简单的确定性规则。为揭示不同物理上相异的遍历行为类别，我们对三态细胞自动机（含一个稳定的‘真空’态及带±电荷的‘粒子’）开展了系统性研究。该分类借助自动机在离散对称性（电荷共轭、空间宇称和时间反演）下的不同变换性质予以辅助。特别地，我们提出一种简洁分类方案，依据如下可观测量来区分此类系统中遍历行为的类型与层级：平均返回时间、守恒量数目以及关联函数的标度行为。在每一类物理上相异的类别中，我们给出具体示例并讨论其部分现象学特征，包括混沌或遍历动力学、相空间碎片化、Ruelle-Pollicott共振、拟局域守恒量的存在性，以及具有多种动力学指数的反常输运。

诸如 Lenia 这类连续细胞自动机（continuous cellular automata）可自发产生类生命、自推进的图案，其中包括 Orbium 滑翔机（Orbium glider）：它沿直线运动，并以固定的呼吸周期脉动。基于碰撞的逻辑——即通过运动图案之间的碰撞实现计算——已在离散细胞自动机及连续物理介质中确立。而在连续细胞自动机中，计算迄今均需通过对规则进行训练而嵌入，尚不清楚固定规则的自动机（如 Lenia）能否支持通用的基于碰撞的计算。本文基于 Orbium 滑翔机的碰撞构造出一个 INHIBIT 门。在四种连续细胞自动机规则类型所搜索的所有图案中，Orbium 滑翔机是唯一被证实能在与自身副本碰撞后仍完整存留的图案。该门中，一个控制滑翔机将信号滑翔机偏转出其输出路径，因此仅当无控制信号存在时，输出路径才携带信号。该门在呼吸周期全部二十四个相位及控制信号的九个整数偏移量下均能可靠阻断。两个此类门串联构成一个 AND-NOT 链，对全部八种输入组合均正确工作。相比之下，将信号路由至该单一链之外尚未得到验证：偏转后的信号无法恢复至固定着陆位置，且未发现可复用的滑翔机吸收器。因此，Lenia 中基于碰撞计算的当前核心开放问题，已从‘是否存在逻辑门’进一步收窄为‘偏转后的信号能否被准确送达下游逻辑门’——这是将逻辑门扩展至单一直线链之外所必需的下一步。