线性元胞自动机与多状态变量研究

### 线性元胞自动机与多状态变量研究 #### 1. 线性元胞自动机基础 元胞自动机（Cellular Automata, CA）是由无限规则排列的元胞组成的离散时间动态系统。元胞是有限状态机，它们根据局部规则 $f$ 同步改变状态，该规则将元胞的新状态指定为其相邻元胞旧状态的函数。 考虑一个 $D$ 维的 CA，其状态集 $Q$ 是有限的。元胞位于 $D$ 维欧几里得空间的整数格点上，由 $\mathbb{Z}^D$ 索引。系统在任何给定时间的全局状态（或配置）是一个函数 $c : \mathbb{Z}^D \to Q$，它给出所有元胞的状态。记 $C^D_Q$ 为状态集 $Q$ 上所有 $D$ 维配置的集合。 CA 的邻域向量 $N = (v_1, v_2, \ldots, v_n)$ 指定了元胞邻居的相对位置：每个元胞 $x \in \mathbb{Z}^D$ 在位置 $x + v_i$（$i = 1, 2, \ldots, n$）有 $n$ 个邻居。局部规则 $f : Q^n \to Q$ 决定了全局动态 $F : C^D_Q \to C^D_Q$，具体为：对于每个 $c \in C^D_Q$ 和 $x \in \mathbb{Z}^D$，有 $F(c)(x) = f [c(x + v_1), c(x + v_2), \ldots, c(x + v_n)]$，函数 $F$ 称为（全局）CA 函数。 如果状态集 $Q$ 是具有单位元的有限交换环（通常是模 $m$ 的整数环 $\mathbb{Z}_m$），并且局部规则 $f$ 是线性函数 $f(q_1, q_2, \ldots, q_n) = a_1q_1 + a_2q_2 + \ldots + a_nq_n$（其中 $a_1, a_2, \ldots, a_n$ 是环 $Q$ 中的常数），则该元胞自动机称为线性（或加法）元胞自动机。线性特性简化了全局函数 $F$ 的分析，许多对于一般 CA 不可判定的性质在线性情况下有多项式时间算法。 线性局部规则可以用 Laurent 多项式表示。为简单起见，先考虑一维情况 $D = 1$。具有邻域 $N = (v_1, v_2, \ldots, v_n)$ 的局部规则 $f(q_1, q_2, \ldots, q_n) = a_1q_1 + a_2q_2 + \ldots + a_nq_n$ 表示为 Laurent 多项式 $p(x) = a_1x^{-v_1} + a_2x^{-v_2} + \ldots + a_nx^{-v_n}$。该多项式是 Laurent 多项式，因为 $x$ 可以有正负幂。 配置可以表示为 Laurent 幂级数：一维配置 $c$ 对应于形式幂级数 $s(x) = \sum_{i = -\infty}^{\infty} c(i)x^i$。那么 $p(x)s(x)$ 表示配置 $F(c)$，$p^k(x)s(x)$ 表示 $F^k(c)$。 记 $Q[x, x^{-1}]$ 为环 $Q$ 上的 Laurent 多项式集合，它本身是一个（无限）交换环。记 $Q[[x, x^{-1}]]$ 为环 $Q$ 上的 Laurent 级数集合。注意，$Q[[x, x^{-1}]]$ 中的元素可以相加，但不能相互相乘，而 Laurent 级数与 Laurent 多项式的乘积是有定义的。 一个 CA 函数 $F$ 是线性的（即由某个 Laurent 多项式 $p(x)$ 定义），当且仅当它是 $Q[[x, x^{-1}]]$ 的线性变换，即对于所有配置 $c$ 和 $d$，以及所有 $a \in Q$，有 $F(c + d) = F(c) + F(d)$ 和 $F(a \cdot c) = aF(c)$。 经典的元胞自动机结果涉及单射性和满射性问题。如果全局函数 $F$ 是一对一的，则 CA 称为单射的；如果全局函数是满射的，则 CA 称为满射的。以下基本性质在任何维度 $D$ 都成立，并且不仅在线性情况下成立： 1. 每个单射的 CA 也是满射的。 2. 如果 $F$ 是单射的 CA 函数，则其逆 $F^{-1}$ 也是一个 CA 函数，由逆元胞自动机计算。有时单射的 CA 称为可逆的。 3. 一个 CA 函数 $F$ 是满射的，当且仅当 $F$ 在有限配置集上是单射的。（如果相对于状态 $q$，只有有限个元胞处于不同于 $q$ 的状态，则配置 $c$ 称为有限的，该陈述对于任何 $q \in Q$ 都成立。） 在无限制的情况下，很难刻画使 CA 成为单射或满射的局部规则。如果空间至少是二维的，那么甚至无法判定给定的局部规则是否定义了单射或满射的动态（在一维情况下存在决策算法）。 线性性简化了分析。线性单射函数的逆也是线性函数，所以 $p(x)$ 定义一个单射的 CA 当且仅当存在一个 Laurent 多项式 $q(x)$ 使得 $p(x)q(x) = 1$，这样的 $q(x)$ 是逆自动机的局部规则。基于性质 3，$p(x)$ 定义一个满射的 CA 当且仅当不存在非零的 Laurent 多项式 $q(x)$ 使得 $p(x)q(x) = 0$。 以下命题给出了线性 CA 单射性和满射性的判定条件： - **命题 1**：由环 $Q$ 上的多项式 $p(x)$ 表示的线性 CA： - (a) 是满射的，当且仅当 $Q$ 的任何极大理想都不包含 $p(x)$ 的所有系数。 - (b) 是单射的，当且仅当对于每个极大理想，$p(x)$ 恰好有一个系数在理想之外。 - **推论 1**：由环 $\mathbb{Z}_m$ 上的多项式 $a_1x^{v_1} + a_2x^{v_2} + \ldots + a_nx^{v_n}$ 表示的线性 CA： - (a) 是满射的，当且仅当 $\gcd(m, a_1, a_2, \ldots, a_n) = 1$。 - (b) 是单射的，当且仅当 $m$ 的每个素因子 $p$ 整除除了恰好一个系数 $a_1, a_2, \ldots, a_n$ 之外的所有系数。 命题 1 的条件可以重新表述为以下易于检查的单射和满射线性规则的特征： - **命题 2**：由环 $Q$ 上的多项式 $p(x)$ 表示的线性 CA： - (a) 是满射的，当且仅当对于每个 $a \in Q \setminus \{0\}$，有 $a \cdot p(x) \neq 0$。 - (b) 是单射的，当且仅当对于每个 $a \in Q \setminus \{0\}$，存在 $b \in Q$ 使得 $ab \cdot p(x)$ 是一个单项式。 #### 2. 多带线性规则 前面考虑了环 $Q$ 上的线性元胞自动机，其中每个元胞使用相同的线性局部规则。现在通过允许偶数和奇数编号的元胞使用不同的线性规则来推广这种情况。 设 $p_1(x)$ 和 $p_2(x)$ 分别是表示偶数和奇数元胞局部规则的 Laurent 多项式。将多项式中的 $x$ 的偶数和奇数幂分开，即找到 Laurent 多项式 $p_{11}(x)$、$p_{12}(x)$、$p_{21}(x)$ 和 $p_{22}(x)$，使得 $p_1(x) = p_{11}(x^2) + x \cdot p_{12}(x^2)$，$p_2(x) = x \cdot p_{21}(x^2) + p_{22}(x^2)$。 $p_{11}(x)$ 和 $p_{12}(x)$ 分别表示偶数和奇数元胞对偶数元胞的贡献，$p_{21}(x)$ 和 $p_{22}(x)$ 分别表示偶数和奇数元胞对奇数元胞的贡献。如果 $c_1(x)$ 和 $c_2(x)$ 是表示偶数和奇数元胞在任何给定时间状态的 Laurent 幂