元胞自動機/邊界條件

在有界格子上，關於觀察到的字串$\alpha$邊界之外的前像的資訊可以用兩個邊界前像向量（左$b_{L}$ 和 右$b_{R}$）來描述。觀察到的字串$\alpha$ 可以被看作是無限字串$\beta _{L}\alpha \beta _{R}$的一部分。邊界向量$b_{L}$ 描述了半無限字串$\beta _{L}$ 的前像，邊界向量$b_{R}$ 描述了半無限字串$\beta _{R}$ 的前像。向量元素是可以在邊界處從邊界追溯到無窮大的每個重疊的前像的數量。左邊界向量$b_{L}$ 中位置$o_{L}$ 處的元素指定了可以從左無窮大追溯到觀察到的字串左側邊界處的重疊$o_{L}$ 的前像$p_{-\infty \leftrightarrow o_{L}}(\beta _{L})$ 的數量。右邊界向量$b_{R}$ 的定義類似。

$b_{L}=[p_{-\infty \leftrightarrow o_{L}=0},p_{-\infty \leftrightarrow o_{L}=1},\dots ,p_{-\infty \leftrightarrow o_{L}},\dots ,p_{-\infty \leftrightarrow o_{L}=k^{m-1}-1}]^{T}$

$b_{R}=[p_{0=o_{R}\leftrightarrow +\infty },p_{1=o_{R}\leftrightarrow +\infty },\dots ,p_{o_{R}\leftrightarrow +\infty },\dots ,p_{k^{m-1}-1=o_{R}\leftrightarrow +\infty }]^{T}$

由於我們通常不關心 CA 在觀察字串之外的狀態，因此可以使用無限制邊界向量。\paragraph{定義} 對於 \emph{無限制邊界向量}，假設每個邊界重疊都可以用來追蹤到無窮遠處的唯一路徑。因此，無限制邊界向量包含所有 1。

$b_{u}=[1,1,\dots ,1]^{T}$

注意 以下定義依賴於尚未被證明的假設，因此定義可能存在錯誤。

一般邊界向量 $b_{L}$ 和 $b_{R}$ 描述了一般無限字串 $\beta _{L}$ 和 $\beta _{R}$。假設這些字串以無限制邊界向量 $b_{u}$ 在無窮遠處結束。

$b_{L}^{T}=\lim _{|\beta _{L}|\rightarrow \infty }b_{u}^{T}\,D(\beta _{L})\qquad b_{R}=\lim _{|\beta _{R}|\rightarrow \infty }D(\beta _{R})\,b_{u}$

由於無限字串可以有無限個原像，因此此定義很少有用。可以使用布林值代替整數來表示重疊是否可以用於追蹤。方程相同，只是用於矩陣乘法的標量乘法運算子被替換為異或邏輯運算。另一種選擇是使用機率。

另一種常見的邊界是具有有限週期的無限週期字串。一些常用的邊界可以用這種方式定義。週期邊界向量 $b_{\bar {L}}$ 和 $b_{\bar {R}}$ 描述了具有有限週期 ${\overline {\beta _{L}}}$ 和 ${\overline {\beta _{R}}}$ 的無限週期字串。這些字串在無窮遠處以相同的邊界向量 $b_{\bar {L}}$ 和 $b_{\bar {R}}$ 結束。一個長度為 $n$ 的週期字串 ${\overline {\beta }}^{n}$ 的前像矩陣計算為 $D({\overline {\beta }}^{n})=D^{n}({\overline {\beta }})$。

$b_{\bar {L}}^{T}=\lim _{n\rightarrow \infty }b_{\bar {L}}^{T}\,D^{n}({\overline {\beta _{L}}})\qquad b_{\bar {R}}=\lim _{n\rightarrow \infty }D^{n}({\overline {\beta _{R}}})\,b_{\bar {R}}$

這個定義的問題是可能存在許多不同的向量滿足這些條件。本文末尾有一個具有有限數量前像的週期邊界的示例。