Cellular automaton

A cellular automaton is a certain class of mathematical objects of which Conway's Game of Life is an example. It consists of a number of things:

• A positive integer n which is the dimension of the cellular automaton
• A finite set of states S, with at least two members
• A state for the whole cellular automaton is obtained by assigning an element of S to each point of the n-dimensional lattice Zⁿ (where Z is the set of all integers), known as cells
• The concept of a neighbourhood. The neighbourhood N of the origin is some finite (nonempty) subset of Zⁿ. The neighbourhood of any other cell is obtained in the obvious way by translating that of the origin.
• A transition rule, which is a function from S^N to S (that is to say, for each possible state of the neighbourhood the transition rule specifies some cell state).

The state of the cellular automaton evolves in discrete time, with the state of each cell at time t+1 being determined by the state of its neighbourhood at time t, in accordance with the transition rule.

There are some variations on the above definition. It is common to require that there be a quiescent state (i.e., a state such that if the whole universe is in that state at generation 0 then it will remain so in generation 1). In Conway's Game of Life, the "OFF" state is quiescent, but the "ON" state is not. Other variations allow spaces other than Zⁿ, neighbourhoods that vary over space and/or time, probabilistic or other non-deterministic transition rules, and so on.

It is common for the neighbourhood of a cell to be the 3×...×3 hypercube centred on that cell, which is known as its Moore neighbourhood.

External links

• Cellular automaton at the Life Lexicon