セルオートマトンの定義

はじめに
セルオートマトンの定義
状態更新
おわりに

はじめに

ここではセルオートマトン（Cellular Automata; CA）という数理モデルを数学的に定義していきます．
セルオートマトンがどのようなものか知りたい人はここから確認できます．

セルオートマトン $\mathcal{A}$ は次の5つ組で定義されます：

$\mathcal{A} \triangleq (\mathcal{L}, \mathcal{T}, \mathcal{S}, \mathcal{N}, \phi)$

ここで， $\mathcal{L}$ は $d$ 次元格子， $\mathcal{S}$ は状態集合， $\mathcal{T}$ は時間集合， $\mathcal{N}$ は原点近傍， $\phi:\ \mathcal{S}^\mathcal{N} \longrightarrow \mathcal{S}$ は局所規則を表します．
これらがどのように働いていくのかを説明していきます．

まず，次のような写像 $\mathbf{A}^t$ を考えます：

$\begin{array}{cccc} \mathbf{A}^t: & \mathcal{L} & \longrightarrow & \mathcal{S}\\ & \boldsymbol{x} & \longmapsto & \mathbf{A}^t(\boldsymbol{x}) \end{array}.$

ここで， $\mathbf{A}^t(\boldsymbol{x})$ は時刻 $t \in \mathcal{T}$ における点 $\boldsymbol{x} \in \mathcal{L}$ の状態を表します．
また，点 $\boldsymbol{x}$ における近傍を $\mathcal{N}_\boldsymbol{x} \triangleq \{\boldsymbol{x} + \boldsymbol{n} \mid \boldsymbol{n} \in \mathcal{N}\}$ とすれば，

$\mathbf{A}^t(\mathcal{N}_\boldsymbol{x}) \triangleq \{\mathbf{A}^t(\boldsymbol{n}) \mid \boldsymbol{n} \in \mathcal{N}_\boldsymbol{x}\}$

は近傍 $\mathcal{N}_\boldsymbol{x}$ 上の状態集合を表します．

状態更新

局所規則 $\phi$ を基に大域規則 $\Phi$ を次のように定義します：

$\Phi:\ \mathcal{S}^\mathcal{L} \longrightarrow \mathcal{S}^\mathcal{L} \quad \text{s.t.} \quad \Phi(\mathbf{A})(\boldsymbol{x}) \triangleq \phi(\mathbf{A}(\mathcal{N}_\boldsymbol{x})).$

この大域規則に従って，初期状態 $\mathbf{A}^0$ から始まり，時間ステップ $\Delta t$ ごとに状態を更新していきます：

$\Phi(\mathbf{A}^0) = \mathbf{A}^{\Delta t},\quad \Phi(\mathbf{A}^{\Delta t}) = \mathbf{A}^{\Delta t + \Delta t},\quad \cdots \quad, \Phi(\mathbf{A}^t) = \mathbf{A}^{t + \Delta t}.$