Cellular Automata/Mathematical Model

Formally, a cellular automaton is represented by the 4-tuple $\{Z,S,N,f\}$ where:

• $Z$ is the finite or infinite lattice
• $S$ is a finite set of cell states or values
• $I$ is the finite neighborhood
• $f$ is the local transition function defined by the transition table or the rule

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 (one of a finite set of integers). Time is also discrete. The future state of a cell (time $t+1$) is a function of the present state (time $t-1$) of a finite number of cells called the neighborhood.

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 configuration

The infinite global state is a configuration $C\in S^Z$. $S$ is the finite set $|S|<\mathrm{\infty }$ of cell states $c\in S$, for formalization purposes the states are enumerated $S=\{0,1,\dots ,|S|-1\}$. $Z$ is the lattice, the infinite cyclic group of integers $\{...,-1,0,1,2,...\}$. The position of each cell inside the lattice is described by the position index $x\in Z$. Configurations are usually written as strings.

$C=\dots c_{-1}{c}_0{c}_1{c}_2\dots c_{x-1}{c}_x{c}_{x+1}\dots$

The finite global state is a finite configuration $C\in S^Z$, where $Z$ is a finite lattice, a finite set $\{0,1,2,\dots ,N-1\}$ of $N$ integers.

$C=c_0{c}_1\dots c_{x-1}{c}_x{c}_{x+1}\dots c_{N-2}{c}_{N-1}$

Configurations and their parts can be generally written as strings denominated by small greek letters from the beginning of the alphabet. Strings can be compactly written as numbers. Forward Converter

Neighborhood, local transition function and rule

The neighborhood size and position

The cells in the neighborhood $n_x$ of the cell $c_x$ have indexes $x+I_i$, where $I_i\in I$ are values from the set of neighbors $I=\{-r_L,-r_L+1,...,-1,0,1,...,r_R-1,r_R\}$. $r_L$ and $r_R$ are neighborhood sizes to the left and to the right since usually the neighborhood is symmetric a single radius $r$ can be used. The size of the neighborhood is $|I|=m=r_L+1+rR=2r+1$.

$n_x=c_{x-r_L}{c}_{x-r_L+1}\dots c_{x+r_R}$

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

$n_x$	$=\sum _{i=0}^{k-1}{c}_{x+N_i}|S{|}^{k-1-i}=\sum _{i=0}^{k-1}{c}_{x-k_0+i}|S{|}^{k-1-i}$
	$=c_{x-k_0}|S{|}^{k-1}+c_{x-k_0+1}|S{|}^{k-2}+\dots +c_{x-k_0+k-1}|S{|}^0$

The neighborhood cell indexing and the local transition function

The local transition function

$f:S^N\mapsto S$

calculates the value of a single future cell $c_x$ from the neighborhood of the observed cell in the present.

$c_x^{t+1}=f(c_{x-r_L}^t,c_{x-r_L+1}^t,\dots ,c_{x+r_R}^t)$

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

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

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

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

See also

• Cellular Automata/Neighborhood for some frequently used neighborhoods
• Cellular Automata/Rule for some special rules

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_{x-1}{c}_x{c}_{x+1}\dots )=\dots f(c_{x-1-r_L},c_{x-r_L},\dots ,c_{x-1+r_R})f(c_{x-r_L},c_{x-r_L+1},\dots ,c_{x+r_R})f(c_{x+1-r_L},c_{x+2-r_L},\dots ,c_{x+1+r_R})\dots$

Finite lattices and lattice boundaries

The lattice boundary sizes (left and right)

Infinite cellular automata have no boundary, so it's boundary 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 length $l$.

The neighborhood used in the local transition function oversteps the lattice boundary for $r_L$ cells at the left and $r_R$ cells at the right.

There are two common solutions to the overstepping problem:

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

Cyclic boundaries

Cyclic boundaries are frequently used as there is no need to explicitly define the boundary value and no external information is introduced into the CA that could otherwise cause interference at the boundaries.

The state of a finite lattice cellular automata is a configuration in the lattice $S^Z$, where $Z$ is a cyclic group of integers modulo $N$ ($\{0,1,...,N-1\}$).

$C=c_0{c}_1\dots c_{x-1}{c}_i{c}_{x+1}\dots c_{N-1}c\in S$

The cyclic position index is calculated as

$x_{\circ }=xmodNx\le 0\vee x>N$

Explicitly defined boundaries

The lattice boundary (left and right)

Explicitly defined boundaries are less common as the simple constant values are useful only for CA where we observe events on a quiescent background with period 1. 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=\{b_{-k_0},\dots b_{-2},b_{-1},b_l,b_{N+1},\dots ,b_{k-k_0-1}\}b\in S$

For space and time periodic quiescent backgrounds time dependent boundaries can be used $B=B(t)$.

Generalizations

Multidimensional cellular automata

Neighborhood in a 2D lattice

The definition of n-dimensional CA is similar to that of one dimensional CA, the lattice becomes n-dimensional and $k$ and $k_0$ become vectors of length $n$.

2D cellular automata

The 2D lattice can be tiled with cells in different ways:

• square grid (4-fold rotational symmetry)
• triangular grid (3-fold symmetry) or hexagonal grid (6-fold symmetry)
• quasi periodic grid (Penrose tiling)

2D cellular automata are often used to simulate real dynamic systems (fluid and gas dynamics)

See also

• Cellular Automata/Neighborhood for some frequently used neighborhoods

Higher order cellular automata

The CA is of higher order if not only the present but past configurations too are used to calculate the future. A second order local transition function is defined as

$c_x^{t+1}=f(n_x^t,n_x^{t-1})$

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