元胞自动机/计数前像

前像是过去导致当前配置的一步配置。

时间方向的逆转

局部转移函数和全局转移函数定义了元胞自动机在正向时间方向上的演化。要从当前配置计算前像，必须定义正向映射的逆。

单个细胞 $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 是一款用户友好的免费软件，用于根据用户选择的配置查找原像。