Cellular automaton

A cellular automaton consists of cells arranged in a one- or higher-dimensional grid. Each cell has a state chosen from a specified set, often a small finite set such as 0 and 1. At each discrete time step, a transition rule updates cells using the states in a local neighbourhood. In the standard deterministic model, the same rule is applied simultaneously across the grid. The grid, available states, neighbourhood and update rule together determine the automaton.

Although the local rules can be simple, their repeated application may generate intricate patterns or behaviour that is difficult to infer from a single update. Some cellular automata can perform general-purpose computation: appropriate constructions can simulate a Turing machine. This makes cellular automata useful both as objects of mathematical study and as models for exploring how complex behaviour can arise from simple local interactions.

Elementary cellular automata use a one-dimensional row of binary cells, with each update depending on a cell and its nearest neighbours. Different rules produce different patterns; Rule 30 is a widely studied example. In two dimensions, John Conway’s Game of Life uses cells in two states on a square grid and updates them according to neighbour-based rules. It is an example of a cellular automaton, not a separate class of all such systems.

Cellular automata serve as computational models, discrete dynamical-system simulators, and tools for studying pattern formation and complexity. Researchers have used them to represent selected processes in scientific fields. A model's usefulness depends on how its grid, states and rules map onto the system being studied; an automaton that reproduces a pattern does not, by itself, establish that the real process works through the same mechanism.

Cellular automata are associated with the work of mathematicians John von Neumann and Stanislaw Ulam in the 1940s, including investigations of self-reproducing machines and patterns. John Conway later devised the Game of Life, which became a prominent two-dimensional example. Stephen Wolfram's systematic studies from the 1980s helped popularize the classification and exploration of elementary cellular automata.