細胞自動機/規則 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 在 維基百科