全局检索与知识浏览

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

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

均匀分布性（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）相当。

我们研究一类一维二值概率元胞自动机（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$）的行为形成对比——在这些确定性情形下，可能出现额外的渐近态，特别是周期性构型。

我们研究定义在任意群宇宙 $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）时该上界可达。

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

我们研究基于元胞自动机（CA）的门限秘密共享方案，该方案支持匿名重构，即仅依据份额即可恢复秘密，而无需知晓参与者的身份。为此，我们重新审视了基于CA的(2,n)门限方案的基本刻画——该刻画以相互正交拉丁方（MOLS）为理论基础，并将秘密空间重新定义为MOLS族本身；由此构造的新方案可实现对秘密CA规则的匿名重构。最后，我们讨论了可共享的秘密CA数量与恢复阶段计算复杂度之间的权衡关系。

元胞自动机（cellular automata）是定义在格点上的离散动力系统，其中每个格点携带有限状态集，并依据局域确定性规则随时间演化。元胞自动机的重要应用之一是流体的格气模型（lattice gas models），该框架为流体的流体力学行为提供了基于粒子的微观描述。宏观流体方程通过对大量格点与时间步长进行粗粒化（coarse-graining）而涌现，从而提供了一条自下而上的流体力学推导路径。一个著名范例是Frisch-Hasslacher-Pomeau（FHP）模型：一种定义在二维三角格点上的元胞自动机，其粗粒化后可导出二维Navier-Stokes方程。本文通过两项修改构建了FHP模型的宇称破缺推广：引入手性两体碰撞规则，并系统地旋转粒子速度以模拟背景磁场效应。我们证明该元胞自动机导出的流体力学模型具有奇粘度（odd viscosity）——一种表征奇流体（odd fluids）的横向输运系数。我们通过对手性FHP元胞自动机的泊肃叶流（Poiseuille-flow）模拟验证了所解析得到的输运系数。结果表明，本文所提出的手性元胞自动机为微观宇称破缺散射过程与宏观奇流体流体力学之间建立了桥梁。

对于有限字母表上的元胞自动机，双射性已蕴含可逆性；而在无限字母表上，该蕴含关系可能不成立。Ceccherini-Silberstein 与 Coornaert 在《Cellular Automata and Groups》一书中将周期情形下剩余的障碍列为开放问题 2（Open Problem 2）。本文给出了一个精确的群论刻画：一个群 $G$ 是局部有限群，当且仅当对任意字母表 $A$，所有双射元胞自动机 $A^G \to A^G$ 均为可逆元胞自动机。等价地，若 $G$ 不是局部有限群，则对任意无限字母表 $A$，均存在一个双射元胞自动机 $A^G \to A^G$，其逆映射不是元胞自动机。该反例已在可数字母表上实现；其局部规则包含秩轨道（rank track）、方向轨道（direction track）与二进制数据轨道（binary data track）；前向映射沿任意长度的有限有向链呈三角形式，因此其逆映射虽可逐点定义，却不具有统一的有限记忆。由此，开放问题 2 获得肯定回答，且负向结论无需周期性假设。

设 $G$ 是一个群，$\mathbb{K}$ 是一个域，$V$ 是一个 $\mathbb{K}$-向量空间。我们证明：存在一个双射的线性元胞自动机 $V^G \to V^G$，其逆映射不是元胞自动机，当且仅当 $G$ 不是局部有限群且 $\dim_{\mathbb{K}}V \geq |\mathbb{K}|^{\aleph_0}$。该结果解决了 T. Ceccherini-Silberstein 与 M. Coornaert 提出的一个公开问题。

元胞自动机（Cellular Automata）是一种局部计算范式，其复杂行为源于简单函数之间的局部交互。该范式已被用于解释诸多系统，例如生物过程、交通仿真、计算机网络等。在游戏领域，元胞自动机曾应用于《模拟城市》（SimCity）等游戏，并用于生成洞穴或地牢等空间内容。然而，设计有效的局部规则困难且缺乏直观性；尽管元胞自动机可通过演化方法有效构造，但其结果仍可能难以解释。本文提出可编程元胞自动机（Programmable Cellular Automata）的概念，将系统表示为 Python 代码，并将其模块化为局部函数（local functions）与决策函数（decision function）：局部函数接收局部邻域并返回一个值，决策函数则接收所有局部函数的输出并决定下一状态的取值。将元胞自动机拆分为以 Python 编写的模块，有助于理解系统运行机制。我们还探索引入全局函数（global functions），即以整个系统状态为输入并从中计算出某函数值。我们在 PCG Benchmark 中三个不同游戏的关卡生成任务上进行了测试。结果表明，引入全局函数可减少元胞自动机求解问题所需的迭代次数；而仅使用局部函数时，某些问题无法找到可行解。进一步分析所生成的函数，我们发现若干在不同实验中反复出现的通用函数，这不仅有助于理解生成器本身，亦有助于深入理解这些游戏及其关键要素。

众所周知，某些元胞自动机的时空图具有分形结构：例如，模 2 的帕斯卡三角形生成谢尔宾斯基三角形。已有研究表明，当符号集被赋予阿贝尔群结构、且该元胞自动机关于此结构是同态、初始构型具有有限支撑时，此类模式可能出现。此时，其时空图具有与 k-自动性相关的性质。我们证明这些条件可予弱化：阿贝尔群可替换为交换幺半群，初始构型可为 k-自动的，而时空图仍保持相同的正则性。

众所周知，某些元胞自动机的时空图具有分形结构：例如模 2 下的帕斯卡三角形生成谢尔宾斯基三角形。已有研究表明，当字母表被赋予阿贝尔群结构、元胞自动机关于该结构是同态、且初始构型具有有限支撑时，此类模式可能出现；此时时空图具有与 k-自动性相关的性质。本文表明，这些条件可被放宽：阿贝尔群可替换为交换幺半群，初始构型可为 k-自动的，而时空图仍保持相同的正则性。

李雅普诺夫指数刻画动力系统对扰动的敏感性，而完整的李雅普诺夫谱则将其推广至切空间中每一正交方向。对于元胞自动机，该谱几乎总是通过数值方法近似计算，且近似过程十分微妙。本文证明：仿射规则（即其更新函数为输入子集的异或运算再加一常数）具有精确可解的李雅普诺夫谱。仿射规则的布尔雅可比矩阵与构型无关，因此其谱简化为某一固定常数矩阵的奇异值的对数，无需数值模拟，亦不涉及极限过程。其中两种情形具有闭式解：（1）在周期性格点上的仿射元胞自动机，其雅可比矩阵为多层循环矩阵，谱等于该规则梯度模板的离散傅里叶变换，适用于任意空间维度；（2）在任意图上定义的奇偶性规则，其雅可比矩阵即为图的邻接矩阵，故其李雅普诺夫谱为邻接谱绝对值的对数，最大李雅普诺夫指数为邻接矩阵谱半径的对数；此时单点扰动的长时间振幅按被扰动节点的特征向量中心性缩放。将周期性格点视为阿贝尔群的凯莱图，可统一上述两种情形。由于这些谱是精确的，它们亦可作为基准：不仅揭示了先前报道谱中出现的数值伪影，更将谱半径与动力学敏感性之间既往非正式的对应关系提升为严格恒等式。

周期性晶格因其特殊的振动行为已被广泛研究数十年。另一方面，某些类型的非周期晶格可实现周期晶格中无法获得的新现象。本文提出一类受元胞自动机启发的新型非周期晶格。元胞自动机最初作为一种机器自复制算法被提出，此后在计算机科学中得到深入研究。此类算法生成的结构未必具有周期性，却遵循明确定义的规则，并由此产生有趣的图案。本文利用该概念构建遵循此类规则的弹性晶格，并以Ulam-Warburton元胞自动机（UWCA）为例加以演示。从单原子正方晶格出发，构造UWCA晶格并分析其振动行为，结果展现出独特的动力学特性，包括对称的本征频率谱、高重数重复出现的固有频率，以及强局域化的角模态。本文预期，受计算机算法启发的晶格有望揭示新的波动现象，从而超越现有晶格设计的性能。

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

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

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

元胞自动机（CA）被广泛用于土地利用变化的模拟。本研究采用基于矢量的元胞自动机模型，以模拟城市土地利用变化。

空中野火扑救不仅需预测火势蔓延，还需在运行与环境不确定性下设计有效的干预策略。本文提出一种空中野火扑救建模与优化框架，将混合神经元胞自动机（neural-cellular automaton）火灾模型与基于梯度的目标化空中投掷方案设计相结合。该火灾模型利用地形、可燃物及风场数据预测空间异质性的火势蔓延行为；干预模块则确定二值化的投掷动作，并以连续变量表征投掷位置与朝向参数，映射至仿真网格。水与阻燃剂分别建模，体现其不同的抑制效应：前者实现对活跃燃烧的即时削弱，后者实现对未来蔓延的持续抑制。为评估所生成扑救方案的鲁棒性，我们通过蒙特卡洛采样每日火灾状态实现来量化偶然不确定性（aleatoric uncertainty），并通过空间相关预测误差扰动量化认知不确定性（epistemic uncertainty）。基于2020年熊火（Bear Fire）的案例研究表明，该框架可生成协调一致的空中扑救调度方案，以减少总过火面积，并支持面向不确定性的野火干预策略分析。

《计算机、环境与城市系统》；第109卷；第102090页；2024年发表；出版机构：Elsevier

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