2025-11-25T16:01:17.767732

On the order of lazy cellular automata

AlcalÃ¡-Arroyo, Castillo-Ramirez

We study the most elementary family of cellular automata defined over an arbitrary group universe $G$ and an alphabet $A$: the lazy cellular automata, which act as the identity on configurations in $A^G$, except when they read a unique active transition $p \in A^S$, in which case they write a fixed symbol $a \in A$. As expected, the dynamical behavior of lazy cellular automata is relatively simple, yet subtle questions arise since they completely depend on the choice of $p$ and $a$. In this paper, we investigate the order of a lazy cellular automaton $Ï: A^G \to A^G$, defined as the cardinality of the set $\{ Ï^k : k \in \mathbb{N} \}$. In particular, we establish a general upper bound for the order of $Ï$ in terms of $p$ and $a$, and we prove that this bound is attained when $p$ is a quasi-constant pattern.

academic

On the order of lazy cellular automata

基本信息

论文ID: 2510.14841
标题: On the order of lazy cellular automata
作者: Edgar Alcalá-Arroyo, Alonso Castillo-Ramirez (Universidad de Guadalajara, México)
分类: cs.FL (Formal Languages), math.DS (Dynamical Systems), math.GR (Group Theory), nlin.CG (Cellular Automata and Lattice Gases)
发表时间: October 17, 2025
论文链接: https://arxiv.org/abs/2510.14841

摘要

本文研究定义在任意群宇宙 $G$ 和字母表 $A$ 上的最基本的细胞自动机族：惰性细胞自动机(lazy cellular automata)。这类细胞自动机在配置 $A^G$ 上通常表现为恒等映射，只有当读取到唯一的活跃转移 $p \in A^S$ 时，才会写入固定符号 $a \in A$ 。尽管惰性细胞自动机的动力学行为相对简单，但由于完全依赖于 $p$ 和 $a$ 的选择，仍会产生微妙的问题。本文研究惰性细胞自动机 $\tau: A^G \to A^G$ 的阶，定义为集合 $\{\tau^k : k \in \mathbb{N}\}$ 的基数。特别地，建立了 $\tau$ 阶的一般上界，并证明当 $p$ 是准常数模式时可达到此界。

研究背景与动机

要解决的问题: 本文研究惰性细胞自动机的阶(order)，即细胞自动机所有幂次映射构成集合的基数。这是理解细胞自动机代数和动力学性质的重要概念。
问题重要性:
- 细胞自动机的阶捕获了其动力学行为的重要特征
- Kůrka定理表明一维细胞自动机具有有限阶当且仅当它是等连续的
- 惰性细胞自动机是最基本的非平凡细胞自动机族，理解其性质有助于研究更复杂的细胞自动机
现有方法局限性:
- 以往研究主要集中在一维情况且邻域为区间的情形
- 对于任意群宇宙上的惰性细胞自动机阶的一般理论尚不完善
- 缺乏准常数模式情况下的完整刻画
研究动机:
- 建立任意群宇宙上惰性细胞自动机阶的一般理论
- 完善准常数模式情况下的分析
- 为更广泛的细胞自动机研究提供基础工具

核心贡献

建立了惰性细胞自动机阶的一般上界: 在定理2中，用唯一活跃转移 $p$ 和写入符号 $a$ 的性质给出了阶的上界。
证明了有限阶惰性细胞自动机的周期为1: 在命题2中证明，如果惰性细胞自动机具有有限阶，则其周期必为1。
完全刻画了准常数模式的惰性细胞自动机的阶: 在定理1中给出了三种情况下的完整分析，大大推广了之前的结果。
提供了幂等性的充分条件: 在推论3中给出了惰性细胞自动机为幂等的充分条件。
构造了任意给定阶的惰性细胞自动机: 证明了对于每个 $n \geq 2$ ，都存在阶为 $n$ 的惰性细胞自动机。

方法详解

任务定义

研究惰性细胞自动机 $\tau: A^G \to A^G$ 的阶，定义为： $\text{ord}(\tau) := |\{\tau^k : k \in \mathbb{N}\}|$

其中惰性细胞自动机通过局部映射 $\mu: A^S \to A$ 定义，满足：

$e \in S$ （群单位元在邻域中）
存在唯一活跃转移 $p \in A^S$ 使得： $\forall z \in A^S, \mu(z) = z(e) \Leftrightarrow z \neq p$

核心理论框架

1. 基本性质分析

通过引理1-3建立了惰性细胞自动机的基本性质：

模式出现刻画: 模式 $p$ 出现在配置 $x$ 中当且仅当 $x \neq \tau(x)$
支撑集单调性: 对于写入符号 $a$ ，支撑集 $\text{supp}_a(\tau^i(x)) \subseteq \text{supp}_a(\tau^j(x))$ 当 $i \leq j$

2. 阶的上界理论

定义集合 $S_b := p^{-1}\{b\} = \{s \in S : p(s) = b\}$ ，建立上界条件：

定理2: 阶至多为满足以下条件的最小 $n \geq 2$ ：对每个词 $(s_1, \ldots, s_{n-1}) \in (S_a)^{n-1}$ ，存在 $1 \leq i \leq j \leq n-1$ 满足：

$(s_j \cdots s_i)^{-1} \in S_b^{-1}S_a$ ，对某个 $b \in A \setminus \{a\}$ ；或
$(s_j \cdots s_i)^{-1} \in S_{b_1}^{-1}S_{b_2}$ ，对某些不同的 $b_1, b_2 \in A \setminus \{a\}$

技术创新点

群理论方法: 利用群的代数结构分析细胞自动机的迭代行为
模式追踪技术: 通过追踪活跃模式在迭代中的演化来确定阶
准常数模式分类: 根据非常数元素的不同情况进行细致分析
构造性证明: 通过显式构造配置来证明阶的精确值

实验设置

理论验证示例

论文通过多个具体例子验证理论结果：

ECA规则236和136: 展示了如何识别惰性细胞自动机并确定其唯一活跃转移
幂等性例子: 通过具体的邻域和模式验证推论3的条件
任意阶构造: 展示如何构造具有指定阶的惰性细胞自动机

分析方法

使用强归纳法证明关键性质
通过反证法建立必要条件
构造性证明充分条件

主要结果

准常数模式的完整刻画

定理1: 设 $\tau: A^G \to A^G$ 是具有准常数唯一活跃转移 $p \in A^S$ 和写入符号 $a$ 的惰性细胞自动机， $r \in S$ 为非常数元素：

情况1: 若 $a \neq p(s)$ 对所有 $s \in S$ ，则 $\text{ord}(\tau) = 2$
情况2: 若 $r \neq e$ 且 $a = p(r)$ ，则 $\text{ord}(\tau)$ 有限当且仅当存在 $n \geq 2$ 使得 $r^n \in S$ 。此时： $\text{ord}(\tau) = \min\{n \geq 2 : r^n \in S\}$
情况3: 若 $r = e$ 且 $a = p(s)$ 对所有 $s \in S \setminus \{e\}$ ，则有限性条件更复杂，涉及词的子词分析