元胞自动机/规则 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)*

最短的伊甸园序列

01010

滑翔机

以太

(00010011011111)*

参见

1. 规则 110 在 数学世界
2. 规则 110 在 Wolfram 图集
3. Harold V. Mcintosh，规则 110 及其与滑翔机存在的关系
4. 规则 110 在 维基百科