A cellular automaton is a grid of cells, each in one of finitely many states, all updated in lock-step by a local rule applied to a cell's neighbourhood. This concept covers the definition of the grid, neighbourhood and transition rule, deterministic synchronous update, the behaviour of Conway's Game of Life and its gliders and still lifes, and how patterns of activity can be composed to carry and combine signals. It covers the reasoning by which a purely local rule is shown to support arbitrary computation, and the distinction between a rule's simplicity and the complexity of the behaviour it generates.
Cellular automata are discrete dynamical systems consisting of a grid of cells, each holding one of a finite set of states, whose next state is determined synchronously by a fixed local rule (lookup …