元胞自动机/边界条件

在有界格子上，关于观察到的字符串$\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}}$

这个定义的问题是可能存在许多不同的向量满足这些条件。本文末尾有一个具有有限数量前像的周期边界的示例。