A row of cells, each black or white. The next row is determined by each cell's 3-cell neighborhood in the previous row — 8 possible inputs, 2 possible outputs = 2⁸ = 256 different rules. Wolfram classified them into four classes ranging from "trivial" to "universal computation." Rule 110 has been proved Turing-complete; Rule 30 has been used as a cryptographic random-number generator.
rule
init
density (random) 0.50
Wolfram's four classes
Stephen Wolfram (1983) studied all 256 elementary CAs and classified them:
Class 1: dies out completely — every input converges to all-zeros or all-ones (rules like 0, 32, 160). Class 2: settles into stable or periodic patterns — like a clockwork, predictable forever (rules like 4, 8, 12, 36). Class 3: chaotic, statistically self-similar but with no clear pattern. Rule 30 is the canonical example — its single-seed output is so statistically random that Mathematica uses it for RandomInteger. Class 4: localized structures that interact in complex, sometimes computationally universal ways. Rule 110 is proven Turing-complete (Matthew Cook, 2004) — meaning a one-dimensional row of cells following the simplest possible rule can simulate any computer.
The deep claim: computational complexity emerges from the simplest possible recipes. No need for fluid dynamics, no need for chemistry, no need for biology. Just a row of binary cells and a lookup table with 8 entries. This is Wolfram's "principle of computational equivalence" — that almost any system above a low complexity threshold can simulate any other.