# Cellular Automata/Mathematical Model

Formally, a cellular automaton is represented by the 4-tuple where:

- is the finite or infinite
*lattice* - is a finite set of cell
*states*or*values* - is the finite
*neighborhood* - is the
*local transition function*defined by the transition table or the rule

The *lattice* is a finite or infinite discrete regular grid of cells on a finite number of dimensions. Each *cell* is defined by its discrete *position* (an integer number for each dimension) and by its discrete *value* (one of a finite set of integers). Time is also discrete. The future state of a cell (time ) is a function of the present state (time ) of a finite number of cells surrounding the observed cell called the neighborhood.

## One dimensional first order cellular automata[edit | edit source]

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

### Lattice, cell and configuration[edit | edit source]

The infinite global state is a *configuration* . is the finite set of *cell states* , for formalization purposes the states are enumerated . The lattice is the infinite cyclic group of integers . The position of each cell inside the lattice is described by the *position index* . Configurations are usually written as strings.

The finite global state is a *finite configuration* , where is a finite lattice, a finite set of integers.

Finite configurations and their parts can be generally written as strings denominated by small Greek letters from the beginning of the alphabet (, , ...).

#### The number notation for strings[edit | edit source]

Strings can be compactly written as numbers. A string of characters from a set of symbols is translated into a -digit base number. Usually strings are indexed from the left to the right but for the number notation indexing from right to left is more intuitive.

### Neighborhood, local transition function and rule[edit | edit source]

#### Neighborhood[edit | edit source]

The neighborhood of size is defined by the set of relative positions inside the configuration.

By applying the set onto an observed cell the neighborhood of this cell is obtained.

The name neighborhood can be used for booth the set of relative distances and for the actual substring of cells related to an observed cell.

A compact representation of the neighborhood value is a single integer defined as a number of digits base .

For definitions of common neighborhoods see Neighborhoods.

#### Local transition function[edit | edit source]

The *local transition function*

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

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* is a compact representation of the local transition function. It is a single integer defined as a number of digits base .

- See also

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

### Global transition function[edit | edit source]

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

translates the current (present) configuration into the next (future) configuration

The global transition function is defined by the local transition function as

### Finite lattices and lattice boundaries[edit | edit source]

Infinite cellular automata have no boundary, so its boundary description 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 .

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

There are two common solutions to the overstepping problem:

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

#### Cyclic boundaries[edit | edit source]

*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 , where is a cyclic group of integers modulo ().

The cyclic position index is calculated as

#### Explicitly defined boundaries[edit | edit source]

*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 (there is no boundary cell with index 0)

For space and time periodic quiescent backgrounds time dependent boundaries can be used .

## Generalizations[edit | edit source]

### Multidimensional cellular automata[edit | edit source]

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

#### 2D cellular automata[edit | edit source]

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

#### Cellular automata on groups[edit | edit source]

One further generalization of the concept of a CA extends the *n*-dimensional construct. Given a finitely generated group, , and a alphabet, , we may define the configuration space to be . That is, each configuration is a map from into . If is abelian, then the group is isomorphic to some quotient space of and may be regarded as a *n*-dimensional lattice with possibly periodic boundary conditions. This space admits a group action, where where is the inverse of . Any finitely generated group is a metric space, in which the distance between any two elements, can be defined to be the minimum length of the set of paths connecting and on the groups Cayley graph. We define a metric on the configuration space, to be 0 if the two configurations are identical, and the infimum of over the set of such that and disagree at and where denotes the identity element of the group. We define a cellular automata to be a continuous mapping, , that commutes with the group action and an initial configuration . The evolution of the system is defined by .

### Higher order cellular automata[edit | edit source]

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

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