Cellular automata

A cellular automaton is a discrete computational model consisting of a grid of cells, each in one of a finite number of states, that evolves in discrete time steps according to a rule applied uniformly to every cell based on its neighbors' states. The most famous example, John Horton Conway's Game of Life, has four rules and produces behavior of staggering variety — from stable structures to gliders that traverse the grid to universal computers that can simulate any computation.

Cellular automata were studied systematically by John von Neumann in the 1940s as models of self-reproduction. Stephen Wolfram's A New Kind of Science (2002) made the sweeping claim that cellular automata are not just models but the actual substrate of physical reality — the foundation of the computational universe hypothesis. The empirical status of this claim remains contested, but cellular automata have proven enormously productive as tools for understanding how complex behavior emerges from simple local rules, which is itself one of the central problems of systems biology, complexity science, and the study of self-organization.

The lesson of cellular automata is not that the universe is a grid; it is that the gap between rule simplicity and behavioral complexity is larger than our intuitions suggest. Understanding that gap is the work of several generations.