有限细胞自动机族的极限集研究

### 有限细胞自动机族的极限集研究 #### 1. 层次结构关系 在研究有限细胞自动机族的极限集时，我们首先关注不同类别的极限集之间的关系。对于类别 \(k - LIM_x\)（其中 \(x\) 可以是 \(s\) 或 \(u\)，分别代表稳定和不稳定情况），有如下重要结论： - **不可比性**：定理表明，对于 \(k, n \geq 1\)，类 \(k - LIM_s\) 和 \(n - LIM_u\) 是不可比的。这是因为所有的 \(k - LIM_s\) 类都包含有限型子转移（SFT），而所有的 \(k' - LIM_u\) 类都包含非索菲子转移。 - **非完全不相交**：这些类别并非完全不相交。例如，设 \(S = \{0, 1, #\}\)，定义半径为 0 的细胞自动机 \(g_0\) 和 \(g_1\) 如下： - \(g_0(x)_i = \begin{cases} #, & \text{如果 } x_i = # \\ 0, & \text{否则} \end{cases}\) - \(g_1(x)_i = \begin{cases} #, & \text{如果 } x_i = # \\ 1, & \text{否则} \end{cases}\) 此时，族 \(\{g_0, g_1\}\) 的极限集 \(X = \{0, #\}^Z \cup \{1, #\}^Z\)，且一步即可达到。由于这个子转移不是传递的，它不可能是单个稳定细胞自动机的极限集，甚至可以证明它也不是任何不稳定细胞自动机的极限集。 为了证明稳定和不稳定层次结构是无限的，我们需要一些引理和构造。 - **特征值与熵**： - 定义：若 \(A\) 是一个本原整矩阵，\(\lambda_A\) 是其绝对值最大的特征值，\(sp_{\times}(A)\) 是其特征值的无序列表（或多重集），称为 \(A\) 的非零谱。 - 引理：由本原整矩阵 \(A\) 定义的边转移 \(X\) 的熵为 \(\log \lambda_A\)。若由两个本原整矩阵 \(A\) 和 \(B\) 定义的边转移 \(X\) 和 \(Y\) 具有相同的熵，且 \(X\) 可因子映射到 \(Y\)，则 \(sp_{\times}(B) \subset sp_{\times}(A)\)。 - **矩阵构造**： - 我们要找到一族 \(k\) 个矩阵 \(M_i\)，使得对于所有的 \(i\) 和 \(j\) 有 \(\lambda_{M_i} = \lambda_{M_j}\)，但当 \(i \neq j\) 时，\(sp_{\times}(M_i) \not\subset sp_{\times}(M_j)\)。 - 设 \(A = [\lambda]\)（\(\lambda\) 远大于 \(k\)），\(B_i = [i]\)（\(i \in [1, k]\)）。通过选取足够大的 \(\lambda\)，满足引理条件，得到矩阵 \(C_i\)，它们是具有相同最大特征值但非零谱不可比的本原整矩阵。 - 为了确保边转移有均匀配置，我们取 \(C_i\) 的公共幂 \(C_i^p\)，得到以下引理：对于所有 \(k \in N\)，存在一个有限字母表 \(S_k\)，一个符号 \(a \in S_k\) 和一组 \(k\) 个在 \(S_k\) 上的混合边转移 \(\{X_1, \ldots, X_k\}\)，使得当 \(i \neq j\) 时，\(X_i\) 不可因子映射到 \(X_j\)，\(X_i \cap X_j = \infty a \infty\) 且 \(B_1(X_i) \cap B_1(X_j) = a\)。 #### 2. 主要定理证明 有了上述准备，我们可以证明稳定和不稳定层次结构的无限性： - **稳定层次结构**： - 定理：对于所有的 \(k\)，\((k - 1) - LIM_s \subsetneq k - LIM_s\)。 - 证明：设 \(X_i\) 由引理给出，对于每个 \(i\)，有细胞自动机 \(f_i\) 以 \(X_i\)