cellular automaton

A $d$-dimensional cellular automatonis a triple$𝒜=⟨Q,𝒩,f⟩$where:

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

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

3. $f:Q^{𝒩}\to Q$ is the local function.

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

$$F_{𝒜}(c)(z)=f(c(z+{\nu }_1),\mathrm{\dots },c(z+{\nu }_{|𝒩|}))=f\left({c|}_{z+𝒩}\right).$$(1)

Observe that the global function is continuous in the product topology.

Cellular automata are a Turing-complete model of computation.In fact, given a Turing machine,it is straightforward to construct a cellular automatonthat emulates it in real time.On the other hand,given a one-dimensional cellular automaton,there exists a Turing machinethat emulates it in linear timewith 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 programthat 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 descriptionis usually a very difficult task,and may depend on the dimension.As an example,reversibility of the global functionis decidable in dimension $1$ but not in dimension $2$ (or higher).

The definition above can be generalized to the caseof a generic group $G$ acting by translationson the space $Q^G$ of configurations.If

$$L_g(x)=g\cdot x\forall x\in G,$$(2)

then the local function $f:Q^{𝒩}\to Q$($𝒩$ being a finite nonempty subset of $G$)induces $F_{𝒜}:Q^G\to Q^G$via the relation

$$F_{𝒜}(c)(g)=f\left({(c\circ L_g)|}_{𝒩}\right)=f\left({c|}_{g𝒩}\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 actionby defining $F_{𝒜}(c)(g)$ as$f\left({(c\circ L_{g^{-1}})|}_{𝒩}\right)$instead:since this is just a reparametrization of the family $L$,the bulk of the theory does not change.

More to come …