元胞自动机/全局动力学

吸引子盆

在讨论元胞自动机的全局动力学时，状态一词用于描述配置。

以下图表/标题基于状态空间和吸引子盆在DDLab网站上的原始图。子树、吸引子盆以及整个吸引子盆场（对于元胞自动机、随机布尔网络以及一般离散动态网络）可以使用DDLab软件计算和绘制。

状态空间由元胞自动机的所有可用状态组成。它的尺寸是 $S=v^{n}$ ，其中 $n$ 是（有限）格子的大小， $v$ 是值范围或字母表，对于二进制系统， $v=2$ 。 $B$ 是其中一个状态。

轨迹 $A\rightarrow B\rightarrow C$ 由全局转换函数定义。状态 $A$ 是前驱，状态 $C$ 是状态 $B$ 的后继。

如果全局转换函数不是单射，那么状态可能具有多个前驱（原像）。状态 $B$ 的入度是其前驱的数量。状态可能没有前驱，那么它被称为伊甸园。

轨迹可能会遇到以前出现过的状态（如果格子是有限的，它必须遇到），因此它已经进入吸引子循环。点吸引子循环的长度为单个单元格。

通过从吸引子循环上的根状态递归搜索前驱（循环上的前驱除外），直到所有伊甸园状态都被达到，瞬态树被构造。可以从树上的任意状态构造一个子树，子树的根。

通过将瞬态树添加到吸引子循环上的每个状态，吸引子盆被构造。一些吸引子循环可能没有瞬态树，这对于可逆元胞自动机尤其如此。

通过将状态空间中的所有状态分组到各自的吸引子盆中，吸引子盆场被构造。

如果全局转换函数 $F$ 是双射（既单射又满射），那么CA规则是可逆的。

$F$ 是单射的，任何CA配置最多只有一个原像。

$F:X\mapsto Y\qquad \forall x_{1},x_{2}\in \Omega \;[x_{1}\neq x_{2}\Rightarrow F(x_{1})\neq F(x_{2})]$

因此，不存在具有多个前驱配置的配置。

$F$ 是单射的，任何 CA 配置至少存在一个原像。

$F:X\mapsto Y\qquad \forall y\in \Omega \;\exists x[y=F(x)]$

因此，不存在没有前驱配置的配置（所谓的伊甸园）。

使用德布鲁因图可以很容易地确定一维 CA 中是否存在伊甸园状态。

$F$ 是双射的，如果它既是单射又是满射。对于任何配置，都只有一个前驱配置。