# cellular automaton

A $d$-dimensional cellular automaton is a triple $\mathcal{A}=\langle Q,\mathcal{N},f\rangle$ where:

1. 1.

$Q$ is a nonempty set, called alphabet or set of states.

2. 2.

$\mathcal{N}=\{\nu_{1},\ldots,\nu_{|\mathcal{N}|}\}$ is a finite, nonempty subset of $\mathbb{Z}^{d}$, called neighborhood   index.

3. 3.

$f:Q^{\mathcal{N}}\to Q$ is the local function.

The local function of the cellular automaton $\mathcal{A}$ induces, by synchronous application at all points, a global function $F_{\mathcal{A}}$ on $d$-dimensional configurations   $c:\mathbb{Z}^{d}\to Q$:

 $F_{\mathcal{A}}(c)(z)=f\left(c(z+\nu_{1}),\ldots,c(z+\nu_{|\mathcal{N}|})% \right)=f\left(\left.{c}\right|_{z+\mathcal{N}}\right)\;.$ (1)

Cellular automata are a Turing-complete model of computation. In fact, given a Turing machine  , it is straightforward to construct a cellular automaton that emulates it in real time. On the other hand, given a one-dimensional cellular automaton, there exists a Turing machine that emulates it in linear time with respect to the size of the input.

Cellular automata make good tools for qualitative analysis  . In fact, given the description of a cellular automaton, it is straightforward to write a computer program that implements its features. Also, several phenomena in different fields of sciences — from physics to biology to sociology — can be described in terms of finite-range interactions between discrete agents.

On the other hand, retrieving the properties of the global dynamics from the local description is usually a very difficult task, and may depend on the dimension  . As an example, reversibility of the global function is decidable in dimension $1$ but not in dimension $2$ (or higher).

The definition above can be generalized to the case of a generic   group $G$ acting by translations on the space $Q^{G}$ of configurations. If

 $L_{g}(x)=g\cdot x\;\;\forall x\in G\;,$ (2)

then the local function $f:Q^{\mathcal{N}}\to Q$ ($\mathcal{N}$ being a finite nonempty subset of $G$) induces $F_{\mathcal{A}}:Q^{G}\to Q^{G}$ via the relation  $F_{\mathcal{A}}(c)(g)=f\left(\left.{(c\circ L_{g})}\right|_{\mathcal{N}}\right% )=f\left(\left.{c}\right|_{g\mathcal{N}}\right)\;\;\forall c:G\to Q\;.$ (3)

Observe that $L=\{L_{g}\}_{g\in G}$ is a left action, while $(c,g)\mapsto c\circ L_{g}$ is a right action. It is of course possible to only use left action by defining $F_{\mathcal{A}}(c)(g)$ as $f\left(\left.{(c\circ L_{g^{-1}})}\right|_{\mathcal{N}}\right)$ instead: since this is just a reparametrization of the family $L$, the bulk of the theory does not change.

More to come …

Title cellular automaton CellularAutomaton 2013-03-22 19:21:58 2013-03-22 19:21:58 Ziosilvio (18733) Ziosilvio (18733) 5 Ziosilvio (18733) Definition msc 37B15 msc 68Q80 neighborhood (cellular automaton) neighborhood index (cellular automaton) local function (cellular automaton) global function (cellular automaton)