Cellular Automata
Wolfram's 256 elementary 1D cellular automata. A single row of binary cells, a three-cell neighbourhood, and one of 256 possible update rules: that is all it takes to produce order, chaos, self-similarity, and — in Rule 110 — computation universal enough to simulate any Turing machine. Each row of pixels is one generation; time flows downward.
Rule 110 — output bits
binary: 01101110
Notable rules
The rule table
Each cell has two states (0 or 1). At each generation every cell looks at itself and its two nearest neighbours — a three-cell window with 2³ = 8 possible patterns, labeled 7 (111) down to 0 (000). The rule number encodes the output for each pattern as one bit of an 8-bit integer. Rule 110, for example, is 01101110 in binary: pattern 7 (111) → 0, pattern 6 (110) → 1, …, pattern 0 (000) → 0.
The boundary wraps: the grid is topologically a cylinder, eliminating edge effects.
Wolfram's four classes
Stephen Wolfram's empirical survey of all 256 rules identified four qualitative behaviours, now called Wolfram complexity classes:
Class I — converge to uniform state (e.g. Rule 0, 255)
Class II — stable periodic structures (e.g. Rule 4, 108)
Class III — chaotic, aperiodic (e.g. Rule 30, 45)
Class IV — complex, localised structures; potentially universal (e.g. Rule 110)
Rule 110 and universality
Matthew Cook proved in 1994 (published 2004) that Rule 110 is Turing-complete — universal computation emerges from a rule table that fits in a single byte. Gliders, stationary structures, and their collisions serve as the computational substrate. This is among the most striking examples of emergence in any formal system.
Rule 30 as a random number generator
Rule 30 is Class III: its centre column passes statistical randomness tests well enough that Wolfram used it as the default pseudo-random number generator in Mathematica for many years. The pattern generated from a single-cell seed is unpredictable despite being deterministic — a microscopic model of how classical chaos generates apparent randomness.