细胞自动机/规则 110 的例子

形式化定义

众所周知的 1D 二进制 CA 规则 110 定义为 $\langle Z,S,N,f,B\rangle$，其中

• $Z$ 可以是有限或无限的
• $S=\{0,1\}$ 是两个值的集合
• $N=\{-1,0,1\}$ 是大小为 $k=3$ 的邻域，对称半径为 $k_{0}=1$
• $f$ 是局部转移函数规则 $r=110$

000 -> 0
001 -> 1
010 -> 1
011 -> 1
100 -> 0
101 -> 1
110 -> 1
111 -> 0

• $B=\{b_{-1},b_{1}\}$ 是可选边界，通常选择为 $B=\{0,0\}$，以避免干扰全为零的静止背景

德布鲁因图

重叠

相邻单元的邻域重叠

相邻细胞的邻域对于 $k-1=2$ 个细胞是重叠的。 有 $|S|^{k-1}=4$ 种不同的重叠 ${00,01,10,11}$，或以紧凑形式写成 ${0,1,2,3}$.

符号德布鲁因图

规则 110 的符号德布鲁因图

德布鲁因图有 $|S|^{k-1}=4$ 个节点（每个可能的重叠一个）和 $|S|^{k}=8$ 条链接（每个可能的邻域一条）。

$D={\begin{bmatrix}0&1&\cdot &\cdot \\\cdot &\cdot &1&1\\0&1&\cdot &\cdot \\\cdot &\cdot &1&0\end{bmatrix}}$

前像矩阵

有两种前像矩阵，每个可用的单元格状态一个。

$D(0)={\begin{bmatrix}1&0&0&0\\0&0&0&0\\1&0&0&0\\0&0&0&1\end{bmatrix}}\qquad D(1)={\begin{bmatrix}0&1&0&0\\0&0&1&1\\0&1&0&0\\0&0&1&0\end{bmatrix}}$

边界条件

有两种常用的背景，静止背景和以太。

静止背景

静止背景是一个无限序列，周期为 $\alpha ={\overline {0}}$，长度为 $|\alpha |=1$ 个单元格。

无论从单个单元格到无穷大的序列长度如何，该背景总是有两个前像（参见前像网络）。 左右边界向量相等。

$b_{L}=b_{R}=[1,0,0,1]$

以太背景

以太背景是一个无限序列，周期为 $\alpha ={\overline {00010011011111}}$，长度为 $|\alpha |=14$ 个单元格。这是从随机初始配置中出现的普遍背景。

以太配置的原像数量随序列长度 $l$ 趋于无穷而呈指数级增长。使用圆形格点来计算周期 $\alpha$ 的原像数量。

$p=p_{c}(\alpha )^{l/|\alpha |}=2^{l/14}$

由于指数级增长，边界向量并不代表整个无限背景的原像数量，而只代表从周期的原像派生的权重。边界向量的值取决于周期内的位置，在下一张表中，向量是 14 个位置中每一个的列。

 overlaps | boundary vectors
---------------------------------------------------------------------
 00       | 0   0   0   0   2   2   0   0   1   0   0   0   0   0
 01       | 0   0   0   0   0   0   2   0   0   1   1   0   2   0
 10       | 0   0   0   2   0   0   0   1   0   1   0   2   0   0
 11       | 2   2   2   0   0   0   0   1   1   0   1   0   0   2
---------------------------------------------------------------------
 sequence |   0   0   0   1   0   0   1   1   0   1   1   1   1   1

列出原像

有界格点

一个如何在有界格点上列出以太序列原像的例子

$b_{L}=b_{R}=b_{u}$

 overlaps | backward preimage count vectors
----------------------------------------------------------------------
 00       | 0   0   0   0   7   7   7   0   4   4   3   2   2   1   1
 01       | 0   0   0   7   0   0   4   7   0   5   4   3   2   2   1
 10       | 0   0   0   0   7   7   7   0   4   4   3   2   2   1   1
 11       | 7   7   7   7   0   0   0   4   3   3   2   2   1   1   1
----------------------------------------------------------------------
 sequence |   0   0   0   1   0   0   1   1   0   1   1   1   1   1

 overlaps | forward preimage count vectors
----------------------------------------------------------------------
 00       | 1   2   2   2   0   1   1   0   0   1   0   0   0   0   0
 01       | 1   0   0   0   2   0   0   1   0   0   1   1   1   2   2
 10       | 1   0   0   0   1   0   0   0   1   0   1   1   2   2   3
 11       | 1   1   1   1   0   0   0   0   1   1   0   1   1   1   2
----------------------------------------------------------------------
 sequence |   0   0   0   1   0   0   1   1   0   1   1   1   1   1

原像网络的权重

 overlaps | neighborhood (link) weights
----------------------------------------
 000      | 0 0 0 0 0 7 0 0 0 0 0 0 0 0
 001      | 0 0 0 0 0 0 7 0 0 4 0 0 0 0
 010      | 0 0 0 0 0 0 0 4 0 0 2 2 1 2
 011      | 0 0 0 0 0 0 0 3 0 0 2 1 1 2
 100      | 0 0 0 0 7 0 0 0 4 0 0 0 0 0
 101      | 0 0 0 0 0 0 0 0 0 0 3 2 4 2
 110      | 0 0 0 7 0 0 0 0 0 3 0 2 1 1
 111      | 7 7 7 0 0 0 0 0 3 0 0 0 0 0
----------------------------------------
 sequence | 0 0 0 1 0 0 1 1 0 1 1 1 1 1

 overlaps | boundary vectors
----------------------------------------------------------------------
 00       | 0   0   0   0   0   7   7   0   0   4   0   0   0   0   0
 01       | 0   0   0   0   0   0   0   7   0   0   4   3   2   4   2
 10       | 0   0   0   0   7   0   0   0   4   0   3   2   4   2   3
 11       | 7   7   7   7   0   0   0   0   3   3   0   2   1   1   2
----------------------------------------------------------------------
 sequence |   0   0   0   1   0   0   1   1   0   1   1   1   1   1

循环格点

 overlaps | preimage count matrices
---------------------------------------------------------------------------------------
 00       | 0000 0000 0000 0000 0232 0232 0232 0000 0121 0121 0111 0110 0011 0100 1000
 01       | 0000 0000 0000 0232 0000 0000 0121 0232 0000 0221 0121 0111 0110 0011 0100
 10       | 0000 0000 0000 0000 0232 0232 0232 0000 0121 0121 0111 0110 0011 0100 0010
 11       | 0232 0232 0232 0232 0000 0000 0000 0121 0111 0111 0110 0011 0100 0010 0001
---------------------------------------------------------------------------------------
 sequence |     0    0    0    1    0    0    1    1    0    1    1    1    1    1

 overlaps | boundary vectors
---------------------------------------------------------------------
 00       | 0   0   0   0   2   2   0   0   1   0   0   0   0   0
 01       | 0   0   0   0   0   0   2   0   0   1   1   0   2   0
 10       | 0   0   0   2   0   0   0   1   0   1   0   2   0   0
 11       | 2   2   2   0   0   0   0   1   1   0   1   0   0   2
---------------------------------------------------------------------
 sequence |   0   0   0   1   0   0   1   1   0   1   1   1   1   1

子集图转换表

from |  to the left        |  to the right
--------------------------------------------------
0000 |  <-0-0000 <-1-0000  |  0000-0-> 0000-1->
0001 |  <-0-0001 <-1-0100  |  0001-0-> 0010-1->
0010 |  <-0-0000 <-1-0101  |  1000-0-> 0100-1->
0011 |  <-0-0001 <-1-0201  |  1001-0-> 0110-1->
0100 |  <-0-0000 <-1-1010  |  0000-0-> 0011-1->
0101 |  <-0-0001 <-1-1110  |  0001-0-> 0021-1->
0110 |  <-0-0000 <-1-1111  |  1000-0-> 0111-1->
0111 |  <-0-0001 <-1-1211  |  1001-0-> 0121-1->
1000 |  <-0-1010 <-1-0000  |  1000-0-> 0100-1->
1001 |  <-0-1011 <-1-0100  |  1001-0-> 0110-1->
1010 |  <-0-1010 <-1-0101  |  2000-0-> 0200-1->
1011 |  <-0-1011 <-1-0201  |  2001-0-> 0210-1->
1100 |  <-0-1010 <-1-1010  |  1000-0-> 0111-1->
1101 |  <-0-1011 <-1-1110  |  1001-0-> 0121-1->
1110 |  <-0-1010 <-1-1111  |  2000-0-> 0211-1->
1111 |  <-0-1011 <-1-1211  |  2001-0-> 0221-1->

伊甸园序列

正则表达式（表达式左右对称）

0*1(00*1+1(1+00)*010)*1(1+00)*011(0+1)*

最短的 GoE 序列

01010

滑翔机

以太

(00010011011111)*

另请参见

1. 规则 110 在 MathWorld
2. 规则 110 在 Wolfram Atlas
3. Harold V. Mcintosh，规则 110 作为它规则与滑翔机存在的关联
4. 规则 110 在 维基百科