元胞自動機/全域性動力學

吸引子盆

在討論元胞自動機的全域性動力學時，狀態一詞用於描述配置。

以下圖表/標題基於狀態空間和吸引子盆在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$ 是雙射的，如果它既是單射又是滿射。對於任何配置，都只有一個前驅配置。