细胞自动机与有限型位移映射

Cellular Automata and Shifts of Finite Type

摘要: 本论文中，我们从拓扑动力系统的角度把细胞自动机看作是符号空间上的连续自映射，对细胞自动机的单射、满射、同胚性质进行研究。我们利用拓扑熵的一般性质证明了经典的Garden定理，即一维细胞自动机为同胚映射当且仅当它为单射。并且，利用该方法可以很方便地将Garden定理推广到高维情形，即任意维细胞自动机为同胚映射等价于它为单射。

Abstract: In this paper, we consider the cellular automaton as a continuous self-mapping on the symbol space from the perspective of the topological dynamic system, and study the injective, surjective, and homeomorphic properties of the cellular automata. We use the general properties of topological entropy to prove the classical Garden theorem, that is, a one-dimensional cellular automaton maps is homeomorphic if and only if it is injective. Moreover, using this method, Garden’s theorem can be easily generalized to the high-dimensional situation, that is, the cellular automata of any dimension is homeomorphic mapping equivalent to it being injective.

1. 引言

细胞自动机(Cellular Automata，简称CA)是一种时间、空间和状态均离散的数学模型，由John Von Neumann于1951年正式提出，用于模拟20世纪50年代生命系统中的自我复制现象 [1] 。1969年，G. A. Hedlund首先从数学角度把细胞自动机看作符号空间上的位移映射的自同态，刻画了一维细胞自动机的一些动力学行为，开创了细胞自动机数学理论研究的先河 [2] 。20世纪70年代，数学家J. H. Conway提出了一种能够进行普适计算的、结构简单的二维细胞自动机——“生命游戏(Game of life)”，使得细胞自动机的研究再度兴起 [3] 。20世纪80年代初，Stephen Wolfram引导了细胞自动机理论研究的新阶段 [4] 。他首先提出了一维的状态数为2且邻域半径为1的基本细胞自动机(Elementary Cellular Automata，简称ECA)，并在大量计算机实验的基础上，通过观察待定规则产生的演化行为将基本细胞自动机分为：稳定、周期、混沌和复杂4类 [5] [6] [7] 。随后，Leon O. Chua等人利用非线性动力学的一套方法严格分析了Wolfram的经验主义观察结果 [8] [9] [10] [11] 。发展至今日，细胞自动机的理论已经十分成熟，而且有了很好的拓展。

本篇文章中，我们从拓扑动力系统的角度对细胞自动机的单射、满射、同胚性质进行研究。设X是符号空间， $\sigma$ 是X上的位移映射，称映射 $f:X\to X$ 是细胞自动机，如果f连续且 $f\circ \sigma =\sigma \circ f$，即是把细胞自动机看作是符号空间上的连续自映射。我们利用拓扑熵的一般性质证明了经典的Garden定理，即一维细胞自动机为同胚映射当且仅当它为单射 [12] [13] 。并且，利用该方法可以很方便地将Garden定理推广到高维情形，即任意维细胞自动机为同胚映射等价于它为单射。最后我们给出了基本细胞自动机中所有的同胚映射，以及几个是满射但不是同胚映射的细胞自动机的例子。

2. 预备知识

在本节中，我们将介绍细胞自动机，符号系统和拓扑熵的概念。首先说明一些动力系统中的记号：

我们用 $\left(X,T\right)$ 表示拓扑动力系统，即X是一个紧致度量空间， $T:X\to X$ 是连续映射；用 $\alpha ,\beta$ 等表示X的开覆盖。记 $\alpha \vee \beta =\left\{A\cap B:A\in \alpha ,B\in \beta \right\}$，则 $\alpha \vee \beta$ 也是X的开覆盖。

2.1. 符号系统

2.1.1. 一维符号系统

设整数 $k\ge 2$，任取k个不同符号，例如取 $0,1,\cdots ,k-1$，记 $S=\left\{0,1,\cdots ,k-1\right\}$，称S为k个符号组成的

状态空间，其中每一个符号也称作状态。赋S以离散拓扑，则S为紧致拓扑空间 [14] 。

作拓扑积

$S^Z={\displaystyle \underset{-\infty }{\overset{+\infty }{\prod }}S=\left\{x=\left(\cdots ,x_{-1},\stackrel{*}{x_0},x_1,\cdots \right):x_i\in S,\forall i\in Z\right\}}$，

这里的Z表示全体整数的集合，记号*表示x中第0个符号(坐标)所在的位置。

对 $\forall x=\left(\cdots ,x_{-1},\stackrel{*}{x_0},x_1,\cdots \right),y=\left(\cdots ,y_{-1},\stackrel{*}{y_0},y_1,\cdots \right)\in S^Z$，定义

$d\left(x,y\right)={\displaystyle \underset{i=-\infty }{\overset{\infty }{\sum }}\frac{\rho \left(x_i,y_i\right)}{2^{\left|i\right|}}}$，

其中

$\rho \left(x_i,y_i\right)=\{\begin{array}{cc}0,& x_i=y_i,\\ 1,& x_i\ne y_i.\end{array}$

容易证明，d是 $S^Z$ 上的度量，且它诱导的拓扑与乘积拓扑等价。文 [14] [15] [16] 中证明了 $\left(S^Z,d\right)$ 是

一个完备的，完全不连通的紧致空间。称 $S^Z$ 为一维k-符号序列空间，简称为一维符号空间。

在 $S^Z$ 上定义位移映射：

$\begin{array}{c}\sigma :S^Z\to S^Z\\ \left(\cdots ,x_{-1},\stackrel{\ast }{x_0},x_1,\cdots \right)\mapsto \left(\cdots ,x_0,\stackrel{\ast }{x_1},x_2,\cdots \right)\end{array}$

即在 $\sigma$ 的作用下， $S^Z$ 中点的坐标依次向左移动一位，因此，也称 $\sigma$ 为左移映射。称 $\left(S^Z,\sigma \right)$ 为S上的一维符号系统。

2.1.2. 二维符号系统

仍记 $S=\left\{0,1,\cdots ,k-1\right\}$ 为 $k\left(k\ge 2\right)$ 个符号组成的集合，记 $S^{Z^2}=\left\{x=\left(x_{i,j}\right):x_{i,j}\in S,\left(i,j\right)\in Z^2\right\}$。对于每一个 $x=\left(x_{i,j}\right)\in S^{Z^2}$，用记号*表示第(0, 0)个符号(因子)所在的位置，即

$x=\left(x_{i,j}\right)=\left(\begin{array}{ccccc}& ⋮& ⋮& ⋮& \\ \cdots & x_{1,-1}& x_{1,0}& x_{1,1}& \cdots \\ \cdots & x_{0,-1}& \stackrel{\ast }{x_{0,0}}& x_{0,1}& \cdots \\ \cdots & x_{-1,-1}& x_{-1,0}& x_{-1,1}& \cdots \\ & ⋮& ⋮& ⋮& \end{array}\right)$

在 $S^{Z^2}$ 中定义距离为

$d\left(x,y\right)=\underset{\left(i,j\right)\in Z^2}{\max }\left\{\frac{1}{\max \left\{\left|i\right|,\left|j\right|\right\}+1}:x_{i,j}\ne y_{i,j}\right\}$。

显然上述定义是合理的。文 [17] 证明了度量空间 $\left(S^{Z^2},d\right)$ 是紧致的、完备的、完全不连通的Huasdorff

空间，并称 $S^{Z^2}$ 为二维k-符号序列空间，简称二维符号空间。

分别对两个坐标定义位移映射 ${\sigma }_1,{\sigma }_2$ 为 ${\left[{\sigma }_1\left(x\right)\right]}_{j_1,j_2}=x_{j_1+1,j_2}$， ${\left[{\sigma }_2\left(x\right)\right]}_{j_1,j_2}=x_{j_1,j_2+1}$。其中 ${\left[{\sigma }_i\left(x\right)\right]}_{j_1,j_2}$ 表示 ${\sigma }_i\left(x\right)$ 中 $\left(j_1,j_2\right)$ 位置的元素 $\left(i=1,2\right)$。称 $\left(S^{Z^2};{\sigma }_1,{\sigma }_2\right)$ 为S上的二维符号系统。类似地，可以定义d维符号系统。

2.2. CA的定义

细胞自动机(Cellular Automata，简称CA)是一类时间、空间和状态均离散的数学模型。构成细胞自动机的四个基本要素分别是：细胞(cell)、网格(lattice)、邻域(neighborhood)和规则(rule) [18] 。最简单的情况下细胞可以取0和1两个状态；网格是指细胞活动的空间；邻域一般指某个细胞自身及其直接相邻的细胞，常见的邻域有Neumann邻域和Moore邻域 [7] ；规则则规定了细胞间的相互作用方式。

1969年，数学家G. A. Hedlund给出如下细胞自动机的定义 [2] ：

定义2.1 设f是 $S^Z$ 上的连续映射，如果紧致系统 $\left(S^Z,f\right)$ 满足条件 $f\circ {\sigma }_L={\sigma }_L\circ f$，则称f是一个一

维细胞自动机，其中 $S^Z$ 表示定义在状态集S上的符号空间， ${\sigma }_L$ 为左移映射。

类似于一维细胞自动机的定义方式，我们可以定义高维细胞自动机。

定义2.2 设f是 $S^{Z^d}$ 上的连续映射，如果紧致系统 $\left(S^{Z^d},f\right)$ 满足条件 $f\circ {\sigma }_i={\sigma }_i\circ f$ $\left(i=1,2,\cdots ,d\right)$，则称f是一个d维细胞自动机，其中 $S^{Z^d}$ 表示定义在状态集S上的d维符号空间， ${\sigma }_i$ 为第i个坐标上的位移映射，即 ${\left[{\sigma }_i\left(x\right)\right]}_{j_1,\cdots ,j_i,\cdots ,j_d}=x_{j_1,\cdots ,j_i+1,\cdots ,j_d}$， $\forall x\in S^{Z^d},i=1,2,\cdots ,d$。其中 ${\left[{\sigma }_i\left(x\right)\right]}_{j_1,\cdots ,j_i,\cdots ,j_d}$ 表示 ${\sigma }_i\left(x\right)$ 中 $\left(j_1,\cdots ,j_i,\cdots ,j_d\right)$ 位置的元素。

2.3. 拓扑熵的定义

动力系统中拓扑熵的定义有多种方法，这里我们用开覆盖来定义 [19] 。

设 $\left(X,T_1\right)$ 是一个拓扑动力系统， $\alpha$ 是X的一个开覆盖，用 $N\left(\alpha \right)$ 表示 $\alpha$ 的子覆盖的基数的下确界，即 $N\left(\alpha \right)=\inf$ { $\beta$ : $\beta$ 是 $\alpha$ 的子覆盖}。因为X是紧致的，所以 $N\left(\alpha \right)$ 是一个正整数。定义开覆盖 $\alpha$ 的拓扑熵为 $H\left(\alpha \right)=\log N\left(\alpha \right)$。

定义2.3 设 $\left(X,T\right)$ 是一个拓扑动力系统， $\alpha$ 是X的一个开覆盖，定义T关于 $\alpha$ 的拓扑熵为

$h\left(T,\alpha \right)=\underset{n\to \infty }{\lim }\frac{1}{n}H\left({\vee }_{i=0}^{n-1}{T}^{-i}\alpha \right)$，T的拓扑熵为 $h\left(T\right)=h\left(X,T\right)=\underset{\alpha }{\sup }h\left(T,\alpha \right)$，其中 $\alpha$ 取遍X的开覆盖。

下面给出与拓扑熵相关的几个命题：

命题2.1 设 $\left(X,T_1\right),\left(X,T_2\right)$ 是两个拓扑动力系统且拓扑共轭(即存在同胚映射 $\pi :X\to Y$，使得 $\pi \circ T_1=T_2\circ \pi$ )，则 $h\left(T_1\right)=h\left(T_2\right)$。也就是说拓扑熵是一个拓扑共轭不变量。

命题2.2 设 $\left(X,\sigma \right)$ 是一维符号系统，则 $h\left(\sigma \right)=\log k$。

命题2.3 设 $\left(X,\sigma \right)$ 是一维符号系统。如果 $X_1$ 是X的闭子集，且 $\sigma \left(X_1\right)=X_1$，那么 $\sigma$ 限制在 $X_1$ 上的拓扑熵为：

$h\left({\sigma |}_{X_1}\right)=\underset{n\to \infty }{\lim }\frac{1}{n}\log {\theta }_n\left(X_1\right)$，

其中 ${\theta }_n\left(X_1\right)$ 表示使得集合 $\left\{{\left(x_i\right)}_{-\infty }^{+\infty }\in X_1:x_j=i_j,j=0,1,\cdots ,n-1\right\}$ 非空的n-元组 $\left[i_0,i_1,\cdots ,i_{n-1}\right]$ 的个数。

类似于命题2.3中一维符号系统拓扑熵的定义方式，Berger在文 [20] 中给出了二维符号系统拓扑熵的如下定义：

定义2.4 设 $\left(X;{\sigma }_1,{\sigma }_2\right)$ 是一个二维符号动力系统，Y是X的子系统，定义 $\left(Y;{\sigma }_1,{\sigma }_2\right)$ 的拓扑熵为

$h\left(Y;{\sigma }_1,{\sigma }_2\right)=\underset{n\to \infty }{\lim }\frac{1}{n^2}\log {\theta }_{n\times n}\left(Y\right)$，

其中 ${\theta }_{n\times n}\left(Y\right)$ 表示使得集合 $\left\{x_{i,j}\in Y:x_{i,j}=a_{i,j},i,j=0,1,\cdots ,n-1\right\}$ 非空的 $n\times n$ -元组

$\left[\begin{array}{ccc}{a}_{0,0}& \cdots & a_{0,n-1}\\ ⋮& \ddots & ⋮\\ a_{n-1,0}& \cdots & a_{n-1,n-1}\end{array}\right]$

的个数。

根据Berger的定义，显然有 ${\theta }_{n\times n}\left(X\right)=k^{\left(n^2\right)}$，因此 $h\left(X;{\sigma }_1,{\sigma }_2\right)=\log k$。

命题2.4 设 $\left(X;f_1,f_2\right)$ 和 $\left(Y;g_1,g_2\right)$ 是两个二维符号系统且拓扑共轭，即存在X到Y的同胚映射 $\pi$，使得 $\pi \circ f_1=g_1\circ \pi$，。那么， $h\left(X;f_1,f_2\right)=h\left(Y;g_1,g_2\right)$ [20] 。也就是说，Berger定义的拓扑熵也是一个共轭不变量。

3. 单射的CA必定是同胚映射

本节我们利用拓扑熵的性质这一方法给出Garden定理的证明，并利用该方法将Garden定理推广到任意维CA的情形。

定理3.1 设 $X={\left\{0,1,\cdots ,k-1\right\}}^{Z^d}$，其中 $d\ge 1$ 是一个整数。再设 $f:X\to X$ 是一个CA，则f是同胚映

射当且仅当f是单射。

为了证明此定理，我们首先给出一个引理：

引理3.1 设 $X={\left\{0,1,\cdots ,k-1\right\}}^{Z^d}$，其中 $d\ge 1$ 是一个整数。再设 $f:X\to X$ 是一个单射的CA，则f是

满射。

证明：我们首先说明一维的情形：

事实上，当 $d=1$ 时，上述结论由Garden-of-Eden定理即可直接得到 [12] [13] 。在这里，我们用拓扑熵的方法进行证明。

假设f不是满的，则 $X\backslash f\left(X\right)$ 是一个非空开集，从而存在柱集 $\left[i_0,i_1,\cdots ,i_{m-1}\right]\subset X\backslash f\left(X\right)$。由细胞自动机定义， $f\circ \sigma =\sigma \circ f$，所以 $f\left(X\right)$ 是 $\sigma$ -不变的。因此， $\left(f\left(X\right),\sigma \right)$ 是具有禁止词“ $i_0{i}_1\cdots i_{m-1}$ ”的有限型位移系统 $\left(Y,\sigma \right)$ 的子系统，即Y中的每个点(双边符号序列)均不含有词“ $i_0{i}_1\cdots i_{m-1}$ ”。下面我们证明 $h\left(Y,\sigma \right)<\log k$。

由定理2.3，

$\begin{array}{c}h\left(Y,\sigma \right)=\underset{n\to \infty }{\lim }\frac{1}{n}\log {\theta }_n\left(Y\right)\\ =\underset{n\to \infty }{\lim }\frac{1}{mn}\log {\theta }_{mn}\left(Y\right)\\ \le \underset{n\to \infty }{\lim }\frac{1}{mn}\log {\left(k^m-1\right)}^n\\ =\frac{1}{m}\log \left(k^m-1\right)<\log k\end{array}$

从而， $h\left(f\left(X\right),\sigma \right)\le h\left(Y,\sigma \right)<\log k$。另一方面，考虑映射 $f:\left(X,\sigma \right)\to \left(f\left(X\right),\sigma \right)$，由于 $f\circ \sigma =\sigma \circ f$，且f是X到 $f\left(X\right)$ 的单射、满射，所以 $\left(X,\sigma \right)$ 与 $\left(f\left(X\right),\sigma \right)$ 在映射f下拓扑共轭。于是， $h\left(f\left(X\right),\sigma \right)=h\left(X,\sigma \right)=\log k$，矛盾。故f是满射。

下面我们说明高维的情形，为了表述方便，我们只对二维的情形给出证明。

类似于 $d=1$ 的证明，我们假设f不是满的。那么 $X\backslash f\left(X\right)$ 是一个非空开集，于是，存在柱集

$\left\{x:x_{j_1,j_2}={\omega }_{j_1,j_2},0\le j_1,j_2\le m-1\right\}\subset X\backslash f\left(X\right)$，其中 $\omega$ 是一个m × m方块。因为 $f\circ {\sigma }_i={\sigma }_i\circ f$，所以 $f\left(X\right)$ 是 ${\sigma }_i$ -不变的 $\left(i=1,2\right)$。因此， $\left(f\left(X\right);{\sigma }_1,{\sigma }_2\right)$ 是具有禁止词 $\omega$ 的有限型位移系统 $\left(Y;{\sigma }_1,{\sigma }_2\right)$ 的子系统，即

Y中的每个点均不含有词 $\omega$。从而，

$\begin{array}{c}h\left(f\left(X\right);{\sigma }_1,{\sigma }_2\right)\le h\left(Y;{\sigma }_1,{\sigma }_2\right)\\ =\underset{n\to \infty }{\lim }\frac{1}{n^2}\log {\theta }_{n\times n}\left(Y\right)\\ =\underset{n\to \infty }{\lim }\frac{1}{{\left(mn\right)}^2}\log {\theta }_{mn\times mn}\left(Y\right)\\ \le \underset{n\to \infty }{\lim }\frac{1}{{\left(mn\right)}^2}\log {\left(k^{\left(m^2\right)}-1\right)}^{\left(n^2\right)}\\ =\frac{1}{m^2}\log \left(k^{\left(m^2\right)}-1\right)<\log k\end{array}$

另一方面，映射 $f:\left(X;{\sigma }_1,{\sigma }_2\right)\to \left(f\left(X\right);{\sigma }_1,{\sigma }_2\right)$ 是一个共轭映射，于是， $h\left(f\left(X\right);{\sigma }_1,{\sigma }_2\right)=h\left(X;{\sigma }_1,{\sigma }_2\right)=\log k$，矛盾，故f是满射。

下面我们给出定理3.1的证明：

证明：充分性是显然的，下面证明必要性：

由一般的拓扑理论，一个从紧致空间到度量空间的连续映射是同胚的，当且仅当它既是单射又是满射 [21] 。由于X是一个紧致度量空间，我们直接通过上述引理即可得到结论。

4. 一些例子

例1 基本细胞自动机(Elementary Cellular Automata，简称ECA)是指状态数为2、邻域半径为1的一维细胞自动机 [4] 。256个基本细胞自动机 $f_i\left(i=0,1,\cdots ,255\right)$ 中的同胚映射有： $f_{15}$， $f_{51}$， $f_{85}$， $f_{170}$， $f_{204}$， $f_{240}$，其中 $f_{170}$ 是恒等映射， $f_{51}$ 是镜像映射， $f_{170}$ 和 $f_{204}$ 分别是左移映射和右移映射， $f_{15}=f_{240}\circ f_{51}$，

$f_{85}=f_{170}\circ f_{51}$ 且 $f_{15}$ 和 $f_{85}$ 是拓扑共轭的。即对 $\forall x=\left(x_i\right)\in {\left\{0,1\right\}}^Z$，有 ${\left[f_{204}\left(x\right)\right]}_i=x_i$， ${\left[f_{51}\left(x\right)\right]}_i=1-x_i$， ${\left[f_{170}\left(x\right)\right]}_i=x_{i+1}$， ${\left[f_{240}\left(x\right)\right]}_i=x_{i-1}$， ${\left[f_{15}\left(x\right)\right]}_i={\left[f_{240}\circ f_{51}\left(x\right)\right]}_i=1-x_{i-1}$， ${\left[f_{85}\left(x\right)\right]}_i={\left[f_{170}\circ f_{51}\left(x\right)\right]}_i=1-x_{i+1}$。

证明：显然 $f_{51}$， $f_{170}$， $f_{204}$， $f_{240}$ 都是单射，所以 $f_{15}$ 和 $f_{85}$ 也是单射。于是，由定理3.1知， $f_{15}$， $f_{51}$， $f_{85}$， $f_{170}$， $f_{204}$， $f_{240}$ 都是同胚映射。下面证明 $f_{15}$ 和 $f_{85}$ 是拓扑共轭的，为此，需构造同胚映射 $\pi$ 使得 $f_{15}\circ \pi =\pi \circ f_{85}$。

在 ${\left\{0,1\right\}}^Z$ 上定义映射 $\pi$ 为：

$\begin{array}{c}\pi :{\left\{0,1\right\}}^Z\to {\left\{0,1\right\}}^Z\\ \left(\cdots ,x_{-1},\stackrel{\ast }{x_0},x_1,\cdots \right)\mapsto \left(\cdots ,x_1,\stackrel{\ast }{x_0},x_{-1},\cdots \right)\end{array}$

即在 $\pi$ 的作用下， ${\left\{0,1\right\}}^Z$ 中点的坐标关于坐标零做了翻转。显然 $\pi$ 是 ${\left\{0,1\right\}}^Z$ 上的同胚映射。

对 $\forall x={\left(x_i\right)}_{-\infty }^{+\infty }\in {\left\{0,1\right\}}^Z,\forall i\in Z$，

${\left[f_{15}\circ \pi \left(x\right)\right]}_i=1-x_{-i-1}=1-x_{-\left(i+1\right)}={\left[\pi \circ f_{85}\left(x\right)\right]}_i$。

因此， $f_{15}\circ \pi \left(x\right)=\pi \circ f_{85}\left(x\right)$。由x的任意性得 $f_{15}\circ \pi =\pi \circ f_{85}$。

例2 满射的CA不一定是同胚，例如ECA中的规则102 (即 $f_{102}$ )是满射，但不是单射，因而不是同胚映射。

证明：由于

$102=2^0\times 0+2^1\times 1+2^2\times 1+2^3\times 0+2^4\times 0+2^5\times 1+2^6\times 1+2^7\times 0$，

在布尔函数真值表中

$\begin{array}{l}N=2^0\cdot f\left(000\right)+2^1\cdot f\left(001\right)+2^2\cdot f\left(010\right)+2^3\cdot f\left(011\right)+2^4\cdot f\left(100\right)\\ +2^5\cdot f\left(101\right)+2^6\cdot f\left(110\right)+2^7\cdot f\left(111\right)\end{array}$，

令 $N=102$，有

$f_{102}\left(000\right)=0,f_{102}\left(001\right)=1,f_{102}\left(010\right)=1,f_{102}\left(011\right)=0$，

$f_{102}\left(100\right)=0,f_{102}\left(101\right)=1,f_{102}\left(110\right)=1,f_{102}\left(111\right)=0$。

于是， $f_{102}\left(x_i\right)=x_i\oplus x_{i+1}$，其中 $\oplus$ 表示逻辑语言“异或”，即 $0\oplus 0=1\oplus 1=0$， $0\oplus 1=1\oplus 0=1$。显然 $f_{102}$ 是满射，下面说明 $f_{102}$ 不是单射。

取 $x=\left(\cdots ,0,\stackrel{\ast }{0},0,\cdots \right),y=\left(\cdots ,1,\stackrel{\ast }{1},1,\cdots \right)\in S^Z$，则有

$f_{102}\left(x\right)=f_{102}\left(y\right)=\left(\cdots ,0,\stackrel{\ast }{0},0,\cdots \right)$。

因此， $f_{102}$ 不是单射。从而， $f_{102}$ 不是同胚。

下面的例子说明存在 ${\left\{0,1\right\}}^Z$ 上的连续自映射f满足：f是单射，但不是同胚。因此，上述的结论要求

所讨论的映射是CA。

例3 设 $X={\left\{0,1\right\}}^Z$，定义映射 $f:X\to X$ 为 ${\left[f\left(x\right)\right]}_{2j}=x_j$， ${\left[f\left(x\right)\right]}_{2j+1}=0$， $\forall x\in X$。也就是说，通过在x的每两个符号之间插入0来构造。容易看出f是连续的，但是，对于任意的 $x\in X$，

$f\circ \sigma \left(x\right)=f\circ \sigma \left(\cdots ,x_{-1},\stackrel{\ast }{x_0},x_1,\cdots \right)=f\left(\cdots ,x_0,\stackrel{\ast }{x_1},x_2,\cdots \right)=\left(\cdots ,x_0,0,\stackrel{\ast }{x_1},0,x_2,\cdots \right)$，

$\sigma \circ f\left(x\right)=\sigma \circ f\left(\cdots ,x_{-1},\stackrel{\ast }{x_0},x_1,\cdots \right)=\sigma \left(\cdots ,x_{-1},0,\stackrel{\ast }{x_0},0,x_1,\cdots \right)=\left(\cdots ,0,x_0,\stackrel{\ast }{0},x_1,0,\cdots \right)$。

所以 $f\circ \sigma \ne \sigma \circ f$，因此f不是CA。进一步，f是单射，但是由于每一个 $f\left(x\right)$ 都不包含长度为2的词“11”，因此f不是满射。

基金项目

国家自然科学基金(编号：11401220)资助。