User:Iztok.jeras~enwiki/Sandbox

Mathematical model

Formally, a cellular automaton is represented by the 5-tuple $\langle Z,S,N,f,B\rangle$ where:

• $Z$ is the finite or infinite lattice
• $S$ is a finite set of cell states or values
• $N$ is the finite neighborhood
• $f$ is the local transition function defined by the transition table or the rule
• $B$ description of the cell space boundary, used only if there are boundaries to be defined

The lattice is a finite or infinite discrete regular grid of finite number of dimensions, filled with cells. Each cell is defined by it's discrete position (an integer number) and by it's discrete value (a finite set of integers). Time is also discrete. The future state of a cell at time $t+1$ is a function of the present state of a finite number of cells called the neighborhood at time $t-1$.

One dimensional first order cellular automata

For the sake of readability the next definitions focus on one dimensional first order cellular automata.

Lattice, cell and configuraton

The global state is a configuration $C$ in $S^{Z}$. $S$ is the finite set $|S|<\infty$ of cell states, for formalization purposes the states are enumetated $S=\{0,1,\dots ,|S|-1\}$. $Z$ is the lattice, the infinite cyclic group of integers $\lbrace ...,-1,0,1,2,...\rbrace$.

$C=\dots c_{-1}c_{0}c_{1}c_{2}\dots$

Neighborhood, local transition function and rule

The neighborhood and the local transition function

The cells in the neighborhood $n_{i}$ of the cell $c_{i}$ have indexes $i+j$, where $j\in N=\lbrace -k_{0},-k_{o}+1\dots -1,0,1\dots k-k_{0}-1\rbrace$ are values from the set of neihbours $N$.

$c_{i-k_{0}},c_{i-k_{0}+1},\dots ,c_{i+k-k_{0}-1}$

A compact representation of the neighborhood value $n_{i}$ is a single integer defined as a number of $k$ digits base $|S|$.

$n_{i}=\sum _{j=1}^{k}{c_{i+N_{j}}|S|^{j-1}}=c_{i-k_{0}}|S|^{k-1}+c_{i-k_{0}+1}|S|^{k-2}+\dots +c_{i+k-k_{0}-1}|S|^{0}$

The local transition function

$f:S^{N}\mapsto S$

calculates the value of a single future cell $c_{i}$ from the neighborhood of the observed cell in the present.

$c_{i}^{t+1}=f(c_{i-k_{0}}^{t},c_{i-k_{0}+1}^{t},\dots ,c_{i+k-k_{0}-1}^{t})$

The transition table defines the local transition function by listing the output value for each input value.

 x  -> f(x)
-----------
000 -> 0
001 -> 0
........
111 -> 0

The rule $r$ is a compact representation of the local transition function. It is a single integer defined as a number of $k$ digits base $|S|$.

$r=f(|S|^{k}-1)|S|^{|S|^{k}-1}+\dots +f(1)|S|^{1}+f(0)|S|^{0}$

Global transition function

The global dynamics of CA are described by the global transition function

$F:S^{Z}\mapsto S^{Z}$

$F$ translates the current (present) configuration $C^{t}$ into the next (future) configuration $C^{t+1}$

$C^{t+1}=F\left(C^{t}\right)$

The global transition function $F$ is defined by the local transition function $f$ as

$F(\dots c_{i-1+k_{0}}c_{i+k_{0}}c_{i+1+k_{0}}\dots )=\dots f(c_{i-1},c_{i},\dots ,c_{i-1+k_{0}-1})f(c_{i},c_{i+1},\dots ,c_{i+k_{0}-1})f(c_{i+1},c_{i+2},\dots ,c_{i+11+k_{0}-1})\dots$

Finite lattices and latice boundaries

File:Cellular automata lattice boundary.png

The lattice boundaries (left and right)

Infinite cellular automata have no boundary, so it's description $B$ is omitted. But there is no way to simulate an infinite system using a finite system. The simulation must focus on a finite part of the infinite lattice.

The state of a finite lattice cellular automata is a configuration in the lattice $S^{Z}$, where $Z$ is the set of $n$ integer cell indexes $\lbrace 0,1,...,n-1\rbrace$

$c_{0}c_{1}\dots c_{i-1}c_{i}c_{i+1}\dots c_{n-1}$

The neighborhood used in the local transition function oversteps the lattice boundary for $k_{0}$ cells at the left and $k-k_{0}-1$ cells at the right.

There are two common solutions to the overstepping problem:

1. the lattice is wraped into a circle (thorus for 2D CA)
2. the values of the overstepping parts of the neighborhood are defined explecitely as the boundary $B$

Cyclic boundaries are frequently used as there is no need to explecetely define the boundary and no external information is introducet into the CA that could otherwise cause interference at the boundaries. $Z$ is a cyclic group of integers modulo $n$ ($\lbrace 0,1,...,n-1\rbrace$). The posittion index is calculated as

$i_{c}=i\mod n\qquad i\leq 0\vee i>n$

Explecitely defined boundaries are less common as the simple constant values are useful only for CA where we observe events on a quiescent background. The boundary can be defined as a single set (the left and the right part combined) of cell values of length $k-1$ (there is no boundary cell with index 0)

$B=\lbrace b_{-k_{0}},\dots ,b_{-1},b_{1},\dots ,b_{k-k_{0}-1}\rbrace \quad b_{i}\in S$

Example

The commonly known 1D binary CA rule 110 is defined as $\langle Z,S,N,f,B\rangle$ where

• $Z$ can be finite or infinite
• $S=\lbrace 0,1\rbrace$ is a set of two values
• $N=\lbrace -1,0,1\rbrace$ is the neighborhood of size $k=3$ with symmetric radius $k_{0}=1$
• $f$ is the next local transition function

000 -> 0
001 -> 0
010 -> 0
011 -> 0
100 -> 0
101 -> 0
110 -> 0
111 -> 0

• $B=\lbrace b_{-1},b_{1}\rbrace$ is the optional boundary usually $B=\lbrace 0,0\rbrace$ choosen not to interfere with the quiescent background of all zeros

Generalizations

Multidimensional Cellular Automata

The definition of nD CA is similar to that of 1D CA, the cell space becomes n-dimensional and k and k₀ become vectors of length n.

Higher Order Cellular Automata

The CA is of higher order if not only the presen but past configurations too are used to calculate the futer.

Seccond order local transition functions are often used to construct reversible rules.

Calculating Cellular Automata preimages

The De Bruijn diagram of a single cell

The De bruijn diagram is a digraph, where vertexes represent all possible overlappings and arcs represent neighborhoods that that are mapped into the observd cell by the local transition function.

Overlapping of adjacent neighborhoods

The overlapping of adjacent neighborhoods (dark gray)

The neighborhoods of a pair of adjacent cells $c_{i}^{t}c_{i+1}^{t}$ are overlapping. The size of the overlapping is one cell less than the size of the neighborhood $k-1$.

$o_{i}=c_{i+1-k_{0}},c_{i+1-k_{0}+1},\dots ,c_{i+1+k-k_{0}-1}$

De Bruijn vector

The De Bruijn vector is a formal representation of vertices of the De Bruijn diagram. It consists of $|S|^{k-1}$ nonnegative integer entries, one for each of the possible neighborhood overlappings. The entries can have different meanings but a common idea is that the value is greater than 0 if it represents the part of a valid preimage.

$d_{i}=[]$

De Bruijn matrix of a single cell

The De Bruijn diagram

The local preimage of a single cell is defined by the inverse of it's local transition function:

$c_{i-k_{0}}^{t-1},c_{i-k_{0}+1}^{t-1},\dots ,c_{i+k-k_{0}-1}^{t-1}=f^{-1}(c_{i}^{t})$

$c_{i+1-k_{0}}^{t-1},c_{i+1-k_{0}+1}^{t-1},\dots ,c_{i+1+k-k_{0}-1}^{t-1}=f^{-1}(c_{i+1}^{t})$

The De Bruijn matrix $D(c)$ is the transition matrix for the De Bruijn diagram. It is a function of the cell value $c$. The size of the metrix is a square $|S|^{k-1}\times |S|^{k-1}$ (the size of the De Bruijn vector).

If the left and the right overlapping represent a neighborhood that maps into the expected output value $c$

Cellular automata neighborhood overlapping

The De Bruijn diagrams are used to describe the local preimage of a

$d_{ij}(={\begin{cases}1,&{\mbox{ if neighborhoods are overlapping }}\\0,&{\mbox{ else }}\end{cases}}$

The De Bruijn matrix of a string of cells

The De Bruijn matrix of a string of cells is the multiplied chain of single cell matrices

$D(c_{p}c_{p+1}\dots c_{q})=D(c_{p})\cdot D(c_{p+1})\cdots D(c_{q})$

Global dynamics of cellular automata

Reversibility of Cellular Automata

The CA rule is reversible, if the global transition function $F$ is bijective (both injective and surjective).

Injectivity of the global transition function

$F$ is injective, there is at most one preimage for any CA configuration.

$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})]$

So there are no configurations with more than one predecessor.

Surjectivity of the global transition function

$F$ is injective, there is at least one preimage for any CA configuration.

$F:X\mapsto Y\qquad \forall y\in \Omega \;\exists x[y=F(x)]$

So there are no configurations without a predecessor (so called Garden of Eden).

Bijectivity of the global transition function

$F$ is bijective if it is both injective and surjective. For any conficuration there is exactly one predecesor.

References

CA deffinition

1. Lyman Hurd, What are Cellular Automata (CA)? [1], CA FAQ
2. Erica Jen, Enumeration of Preimages in Cellular Automata, Complex Systems 3 (1989) 421-456
3. Hidenosuke Nishio, Information Dynamics of Cellular Automata II: Completness, Degeneracy and Entropy
4. Stephen Wolfram, A New Kind of Science

De Bruijn diagram

1. Harold V. McIntosh, Linear Cellular Automata Via de Bruijn Diagrams [2]

Software

1. DDLab by Andy Wuensche