元胞自動機/計數前像

前像是過去導致當前配置的一步配置。

時間方向的逆轉

區域性轉移函式和全域性轉移函式定義了元胞自動機在正向時間方向上的演化。要從當前配置計算前像，必須定義正向對映的逆。

單個細胞 $c_{x}^{t}$ 的前像是由區域性轉移函式的逆定義的區域性有效的鄰域 $n_{x}^{t-1}$

f^{-1}(c_{x}^{t})=\{n_{x}^{t-1}\in S^{N}\;|\;f(n_{x}^{t-1})=c_{x}^{t}\}

配置 $C^{t}$ 的前像 $C^{t-1}$ 由全域性轉移函式的逆定義

F^{-1}(C^{t})=\{C^{t-1}\in S^{Z}\;|\;f(C^{t-1})=C^{t}\}

相鄰細胞的區域性有效鄰域必須正確重疊才能成為全域性有效的。德布魯因圖描述了序列如何重疊，因此提供了一種在知道區域性逆的情況下計算全域性逆的方法。

前像 $C^{t-1}$ 的數量 $p$ 可能從零到很多，具體取決於規則和當前配置 $C^{t}$ ，引發了關於規則的單射性、滿射性和可逆性的問題。

德布魯因圖

德布魯因圖來自描述移位暫存器的理論。它的節點是在某個字母表上的符號串 $w$ ，通常是所有固定長度的字串。它的有向連結描述瞭如果其中一個字串被移動，這些字串如何重疊。這裡只描述了單個細胞的移動。

從源節點 $w_{s}=a\alpha$ 到一個排水節點 $w_{d}=\beta b$ 存在一個連結，如果字串 $w_{s}$ 與字串 $o_{R}$ 重疊，並且向右移動一個符號。這意味著重疊的源子串 $\alpha$ ( $w_{s}$ 去掉起始符號 $a$ ) 等於重疊的排水子串 $\beta$ ( $w_{d}$ 去掉結束符號 $b$ )。

De Bruijn 圖的拓撲矩陣為

d_{w_{s}w_{d}}={\begin{cases}1,&\alpha =\beta \\0,&\alpha \neq \beta \end{cases}}

為了讓該圖更容易在元胞自動機上閱讀和使用，本書使用了一種圖形表示，其中所有節點都被繪製了兩次。左側的節點是連結的源點，右側的節點是連結的排水點。連結的方向選擇為指向細胞位置索引的遞增方向。

另見

關於 De Bruijn 圖的更多資訊請參見參考文獻。

原像圖和矩陣

相鄰鄰域的重疊

重疊 $o_{i}$ 是來自一對相鄰單元格 $c_{x}c_{x+1}$ 的重疊鄰域的單元格組。重疊 $k-1$ 的大小比鄰域的大小少一個單元格。

o_{x}=c_{x+1-k_{0}}c_{x+2-k_{0}}\dots c_{x+k-k_{0}-1}

重疊的緊湊表示是具有 $k-1$ 位基數為 $|S|$ 的數字。

o_{x}=\sum _{i=0}^{k-2}{c_{x+1-k_{0}+i}|S|^{k-2+i}}=c_{x+1-k_{0}}|S|^{k-2}+c_{x+2-k_{0}}|S|^{k-2}+\dots +c_{x+k-k_{0}-1}|S|^{0}

如果一個細胞序列 $...c_{x-2}c_{x-1}c_{x}c_{x+1}c_{x+2}c_{x+3}...$ 在 $c_{x}$ 和 $c_{x+1}$ 之間被切割（或連線）成兩部分，左側部分的最後一個單元格的鄰域 $...c_{x-2}c_{x-1}c_{x}$ 與右側部分的第一個單元格的鄰域 $c_{x+1}c_{x+2}c_{x+3}...$ 重疊。切割（或連線）處的重疊 $o_{x}$ 如上定義，用於描述序列的邊界。

示例:

規則 110 中鄰域的重疊

前像矩陣

構建前像矩陣的第一步是構建一個 De Bruijn 圖，它表示細胞自動機中單個細胞的前像。它的節點是所有 $|S|^{k-1}$ 個不同的鄰域重疊。源節點 $o_{L}$ 是細胞左側的重疊，匯點節點 $o_{R}$ 是細胞右側的重疊。連結表示鄰域 $n$ ，並根據接下來的兩種分解連線節點 $o_{L}$ 和 $o_{R}$ 。

鄰域 $n=c_{L}o_{R}$ 由剩餘的左側單元 $c_{L}$ 和右側重疊 $o_{R}$ 組成，或者
鄰域 $n=o_{L}c_{R}$ 由左側重疊 $o_{L}$ 和剩餘的右側單元 $c_{R}$ 組成。

該圖的拓撲矩陣是一個 $|S|^{k-1}\times |S|^{k-1}$ 元素的方陣。

D=\left[{\begin{matrix}d_{00}&d_{01}&\cdots \\d_{10}&d_{11}&\cdots \\\vdots &\vdots &\ddots \end{matrix}}\right]

如果節點 $o_{L}o_{R}$ 和 $0$ 之間存在連結，則元素的值為 $1$ ，否則為 $0$ 。

d_{o_{L}o_{R}}={\begin{cases}1,&o_{L}c_{R}=c_{L}o_{R}=n\\0,&{\mbox{else}}\end{cases}}

下一步是形成一個符號德布魯因矩陣，其中元素是連結標籤。代表鄰域 $n$ 的連結根據區域性轉移函式定義的輸出單元值 $c=f(n)$ 進行標記。沒有連結的節點對可以用點標記。

d_{o_{L}o_{R}}={\begin{cases}f(n),&o_{L}c_{R}=c_{L}o_{R}=n\\.,&{\mbox{else}}\end{cases}}

最後一步是形成前像矩陣 $D(c)$ ，每個 $|S|$ 個可用的單元格狀態 $c$ 都對應一個矩陣。只有當相對鄰域 $n$ 導致所需的單元格值 $c$ 時，節點對 $o_{L}o_{R}$ 之間才存在連結。

d_{o_{L}o_{R}}(c)={\begin{cases}1,&o_{L}c_{R}=c_{L}o_{R}=n\wedge f(n)=c\\0,&{\mbox{else}}\end{cases}}

示例:

規則 110 中的德布魯因圖和前像圖

序列的前像矩陣

在將前像矩陣的定義擴充套件到單元格序列 $\alpha$ 之前，必須定義矩陣元素的含義，以便可以根據它來檢查定義。

矩陣 $D(\alpha )$ 中的條目 $d_{o_{L}o_{R}}$ 表示長度為 $|\alpha |+k-1$ 的前像的數量，這些前像以左重疊 $o_{L}$ 開頭，以右重疊 $o_{R}$ 結尾。

\alpha ^{t-1}=o_{L}\beta _{R}=\beta _{L}o_{R}\;\wedge \;F(\alpha ^{t-1})=\alpha ^{t}\quad \Rightarrow \quad |F^{-1}(\alpha ^{t})|=d_{o_{L}o_{R}}(\alpha ^{t})

一個細胞串的原像矩陣 $\alpha =c_{p}c_{p+1}\dots c_{q}$ 是單個細胞矩陣的乘積鏈

D(\alpha )=D(c_{p}c_{p+1}\dots c_{q})=\prod _{x=p}^{q}D(c_{x})=D(c_{p})\cdot D(c_{p+1})\cdots D(c_{q})

空字串的原像矩陣 $\varepsilon$ 是一個單位矩陣.

D(\varepsilon )=I

證明： 序列原像矩陣方程的證明 $\Box$

原像邊界條件

原像向量 包含 $|S|^{k-1}$ 個非負整數條目，每個條目對應原像圖中一個可能的鄰域重疊或節點。

原像向量 $b_{x}$ 中的元素 $p_{i}$ 統計包含重疊 $o_{x}=i$ 的原像，該重疊在當前細胞序列中的位置 $x$ 處具有值 $i$ 。

b_{x}=[p_{0},p_{1},\dots ,p_{i-1},p_{i},p_{i+1},\dots ,p_{|S|^{k-1}-1}]

原像向量用於描述邊界，更準確地說，它可以描述兩個字串連線處一側的原像計數。

對於字串 $\alpha =\dots c_{x-1}c_{x}$ 的右邊界，使用右邊界向量 $b_{R}$ ，它統計連線處右側的原像。
為了描述字串 $\alpha =c_{x+1}c_{x+2}\dots$ 的 左側邊界，使用 左側邊界向量 $b_{L}$ ，它從連線點向左計算前像。

無限制邊界 通常用於避免任何特定的邊界。假設每個重疊只有一個前像。向量中的所有條目都是 $1$ 。

b_{u}=[1,1,\dots ,1]\qquad |b_{u}|=|S|^{k-1}

由於 半無限序列 可能有無限多個前像，通常只使用週期性序列，只計算週期 $\alpha$ 的前像。

b_{L}=b_{u}D(\alpha )\,

b_{R}=D(\alpha )b_{u}^{T}

靜止和以太背景可以用週期性序列表示。

另見

細胞自動機/邊界條件瞭解更多關於邊界條件的資訊。

示例:

規則 110 中一些常見的邊界條件。

計算前像。

序列 $\alpha$ 的前像數量 $p$ （網路中的路徑）定義為左邊界條件 $b_{L}$ 和右邊界條件 $b_{R}$ 。

p=b_{L}D(\alpha )b_{R}^{T}

無限制邊界通常用於計算序列 $D(\alpha )$ 的所有前像，每個前像只計算一次。前像的數量僅僅是前像矩陣 $D(\alpha )$ 中所有元素的總和。

p=b_{u}D(\alpha )b_{u}^{T}\,

迴圈細胞串的前像。

由於迴圈格中的字串必須在其左右兩側具有相同的重疊，因此只有德布魯因矩陣對角線上的元素才是有效的前像。字串 $\alpha$ 的所有前像的數量是對角線上元素的總和。

p=\sum _{i=0}^{|S|^{k-1}}d_{ii}(\alpha )

伊甸園

伊甸園序列沒有前像。對於無限格上的有限字串，這在德布魯因矩陣為零矩陣 $M_{0}$ （所有元素都為零）時是完全正確的。

D(\alpha )=M_{0}\Rightarrow \alpha \in G

任何其子串為伊甸園的字串都是伊甸園。

\forall \beta _{L},\beta _{R}\;[\alpha \in G\Rightarrow \beta _{L}\alpha \beta _{R}\in G]

伊甸園可能是邊界條件的結果，包括有限或迴圈邊界條件。

示例:

規則 110 中的伊甸園序列

證明

序列前像矩陣方程的證明

序列公式的證明是關於字串長度的歸納法。

基礎案例 ( $l=0,1$ ): 如果字串的長度為 $0$ ，則沒有偏移，並且節點僅與其自身連結。; 對於長度為 $1$ 的字串，單個單元格前像矩陣元素的含義從定義中可以明顯看出。
歸納: $D(\alpha a)=D(\alpha )D(a)\,$

參考文獻

Harold V. McIntosh，透過德布魯因圖的線性元胞自動機，1991 年 8 月 10 日 (HTML，PDF)
Harold V. McIntosh，祖先：關於 Andrew Wuensche 和 Mike Lesser 的《元胞自動機的全域性動力學》（Addison-Wesley，1992）的評論，1993 年 7 月 20 日 (HTML，PDF)
Erica Jen，元胞自動機中前像的列舉，複雜系統 3 (5) (1989) 421-456
Burton Voorhees，元胞自動機狀態的前驅 II. 有限序列的前像，Phisica D 73 (1-2) (1994) 136-151
Iztok Jeras，Andrej Dobnikar 計算元胞自動機配置前像的演算法 PDF

軟體

DDLab 用於研究元胞自動機、隨機布林網路、多值離散動力系統等的工具；由 Andy Wuensche 提供。
Iztok Jeras，用於計算元胞自動機配置的原像的演算法 TAR.BZ2
元胞自動機原像生成器 CAPIG 是一款使用者友好的免費軟體，用於根據使用者選擇的配置查詢原像。