Elementary cellular automaton

An elementary cellular automaton is a one-dimensional, binary-state cellular automaton in which each cell updates based on its own state and the states of its two immediate neighbors (the left and right cells). The neighborhood thus consists of three binary cells, yielding 2^3 = 8 possible neighborhood configurations. The update rule maps each of these 8 configurations to a new state (0 or 1), giving 2^8 = 256 possible rules — exhaustively enumerable and individually analyzable.

Despite their radical simplicity, elementary cellular automata exhibit the full spectrum of dynamical behavior: fixed points, periodic oscillation, chaotic propagation, and complex localized structures. Rule 110, an elementary rule, was proven Turing-complete by Matthew Cook in 2002 — the simplest known rule with universal computational power. Rule 30 generates pseudo-random sequences from deterministic rules and is used in the Mathematica random number generator. Rule 90 and Rule 150 produce fractal patterns (Sierpiński triangles) from simple seeds.

The elementary cellular automaton is the hydrogen atom of complex systems: the minimal configuration space in which emergence, chaos, computation, and self-organization all appear. If you cannot understand dynamics in 256 rules, you will not understand it in infinite-dimensional state spaces.