Cellular automaton

Summary

A cellular automaton is a grid of cells, each in one of finitely many states. All cells update at the same time by one local rule. The new state of a cell depends only on the old states of the cells in a fixed finite neighbourhood. As a dynamical system it is a continuous map of the configuration space that commutes with the shifts, by the Curtis–Hedlund–Lyndon theorem. Very simple rules can produce complex behaviour, so cellular automata serve as models in physics and biology and as a model of computation.