非均匀元胞自动机的复杂性

### 非均匀元胞自动机的复杂性 在物理学和计算机科学领域，元胞自动机（CA）和非均匀元胞自动机（ν - CA）是研究复杂系统行为的重要工具。本文将深入探讨非均匀元胞自动机的一些关键性质，包括数守恒、满射性、单射性以及线性 rν - CA 的等连续性和敏感性，并分析相关语言的复杂性。 #### 1. 基本概念 在开始深入研究之前，我们先明确一些基本概念。 - **子转移（Subshift）**：对于所有双无限字 $x$，若不存在字 $u \in F$ 出现在 $x$ 中，则所有这样的 $x$ 构成的集合记为 $X_F$。一个双无限语言 $X$ 是子转移当且仅当 $X = X_F$，其中 $F \subseteq A^*$，$F$ 称为 $X$ 的禁止字集合。若 $F$ 是有限集，则 $X$ 是有限型子转移；若 $F$ 是有理集，则 $X$ 是索菲子转移。 - **非均匀元胞自动机的性质**： - **满射性**：一个 $\nu - CA$ 是满射的，当且仅当它的定义映射 $H : A^Z \to A^Z$ 是满射。 - **单射性**：一个 $\nu - CA$ 是单射的，当且仅当它的定义映射 $H : A^Z \to A^Z$ 是单射。 - **等连续性**：对于任意 $\epsilon > 0$，存在 $\delta > 0$，使得对于所有 $x, y \in A^Z$，当 $d(y, x) < \delta$ 时，对于所有 $n \in N$，都有 $d(H^n(y), H^n(x)) < \epsilon$。 - **敏感性**：存在一个常数 $\epsilon > 0$，对于任意元素 $x \in A^Z$ 和任意 $\delta > 0$，存在一个点 $y \in A^Z$，使得 $d(y, x) < \delta$ 且对于某个 $n \in N$，有 $d(H^n(y), H^n(x)) > \epsilon$。 #### 2. 数守恒 在物理学中，许多变换是守恒的，即某个量在整个实验过程中保持不变，例如质量和能量守恒定律。CA 和 $\nu - CA$ 常被用于表示物理现象，因此判断它们何时表示守恒变换是很有意义的。 - **定义**： - **有限配置上的数守恒（FNC）**：一个 $\nu - CA$ $H$ 在有限配置上是数守恒的（FNC），如果对于所有有限配置 $x$，有 $\mu(x) = \mu(H(x))$，其中 $\mu_n(x) = \sum_{i = -n}^{n} x_i$ 是 $x$ 在索引 $-n$ 到 $n$ 之间的部分电荷，$\mu(x) = \lim_{n \to \infty} \mu_n(x)$ 是 $x$ 的全局电荷。 - **数守恒（NC）**：一个 $\nu - CA$ $H$ 是数守恒的（NC），当且仅当满足两个条件：1）$H(0) = 0$，2）对于所有 $x \in A^Z \setminus \{0\}$，有 $\lim_{n \to \infty} \frac{\mu_n(H(x))}{\mu_n(x)} = 1$。 - **性质**：一般情况下，一个 $\nu - CA$ 可以是 FNC 但不是 NC。例如，设 $H : A^Z \to A^Z$ 是一个 $\nu - CA$，对于所有配置 $x$ 和所有整数 $i$，有 $H(x)_{2i} = x_i$ 且 $H(x)_{2i + 1} = 0$，则 $H$ 是 FNC 但不是 NC。然而，对于半径为 $r$ 的 $r\nu - CA$，它是 NC 当且仅当它是 FNC。 - **定理**：设 $R$ 是一个有限的局部规则集，考虑谓词 $P(\theta) =$ “$H_{\theta}$ 是数守恒的”，则 $L_P$ 是一个有限型子转移。证明过程通过构造禁止字集合 $F$，并证明 $L_P = X_F$。 #### 3. 满射性和单射性 在标准 CA 设置中，单射性等价于可逆性，满射性是许多混沌行为的必要条件。对于 $\nu - CA$，我们将证明诱导满射（或单射）$\nu - CA$ 的分布相关语言是索菲（或 $\zeta$ - 有理）的。 - **满射性**： - **引理**：对于任何固定的 $\theta \in \Theta$，$\nu - CA$ $H_{\theta}$ 是满射的，当且仅当对于所有整数 $i, j$（$i \leq j$），$h_{\theta[i, j]}$ 是满射的。 - **德布鲁因图（De Bruijn Graph）**：设 $R$ 是一个半径为 $r$ 的有限规则集，其德布鲁因图 $G = (V, E)$ 是一个带标签的多边图，其中 $V = A^{2r}$，边 $E$ 是所有形如 $(aw, wb)$ 的对，标签为 $(f, f(awb))$，其中 $a, b \in A$，$w \in A^{2r - 1}$，$f \in R$。 - **定理**：设 $R$ 是一个有限的局部规则集，考虑谓词 $P(\theta) =$ “$H_{\theta}$ 是满射的”，则 $L_P$ 是一个索菲子转移。证明过程通过构造一个自动机来识别禁止字集合 $F$，从而证明 $L_P = X_F$。具体的算法步骤如下： 1. 构建 $R$ 的德布鲁因图 $G$。 2