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