cellular automaton
A $d$dimensional cellular automaton is a triple $\mathcal{A}=\u27e8Q,\mathcal{N},f\u27e9$ where:

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

2.
$\mathcal{N}=\{{\nu}_{1},\mathrm{\dots},{\nu}_{\mathcal{N}}\}$ is a finite, nonempty subset of ${\mathbb{Z}}^{d}$, called neighborhood^{} index.

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(c(z+{\nu}_{1}),\mathrm{\dots},c(z+{\nu}_{\mathcal{N}}))=f\left({c}_{z+\mathcal{N}}\right).$$  (1) 
Observe that the global function is continuous^{} in the product topology.
Cellular automata are a Turingcomplete 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 onedimensional 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 finiterange 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({(c\circ {L}_{g})}_{\mathcal{N}}\right)=f\left({c}_{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({(c\circ {L}_{{g}^{1}})}_{\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 

Canonical name  CellularAutomaton 
Date of creation  20130322 19:21:58 
Last modified on  20130322 19:21:58 
Owner  Ziosilvio (18733) 
Last modified by  Ziosilvio (18733) 
Numerical id  5 
Author  Ziosilvio (18733) 
Entry type  Definition 
Classification  msc 37B15 
Classification  msc 68Q80 
Defines  neighborhood (cellular automaton) 
Defines  neighborhood index (cellular automaton) 
Defines  local function (cellular automaton) 
Defines  global function (cellular automaton) 