Growing arbitrarily complex global behaviour from one fixed rule that looks only at neighbours — from the 256 elementary rules to the Turing-complete Game of Life
Is it possible, with the barest possible device — a row (or sheet) of cells and one fixed rule that looks only at neighbours — to generate arbitrarily complex global behaviour? A cellular automaton (CA) is the minimal test bench for the causal chain "local rule → global behaviour": strip the mechanism down to "cells + local update," and see whether complexity can still grow.
Its origins show the weight of the question. John von Neumann invented CAs in the 1940s to study "a machine that can reproduce itself"; Conway turned them into a popular phenomenon in 1970 with four rules; Wolfram systematically swept all 256 one-dimensional elementary rules in the 1980s and distilled four classes of behaviour. All three were asking the same thing: how low is the floor of order — how few rules does it take before complexity begins to grow?
Elementary cellular automaton (1D):
Conway's Game of Life (2D), with even fewer rules — just four:
Start from a single black cell at the top and stack each moment's row downward to get a spacetime diagram. Both "look at three cells only," yet Rule 90 grows a fractal (the Sierpiński triangle) while Rule 30 grows noise that passes randomness tests — the difference is only that eight-row lookup table.
Taken as a whole, the 256 rules sort into four classes: Class I quickly dies to a uniform state; Class II settles on fixed or periodic structures; Class III is perpetual noise (Rule 30 lives here); Class IV, the rarest, grows localized structures that move and collide, poised at the "edge of chaos" (Rule 110 lives here).
In two dimensions the most famous local structure is the glider: five cells that return to their original form every four steps, shifted one cell over. Using gliders as signals and "glider guns" as sources, you can build logic gates and from there a full universal computer — which is what it means for the Game of Life to be Turing complete.
A CA's greatest use is an existence proof: if you can reproduce some macroscopic pattern with one minimal local rule, you have proven that the pattern needs no central command and needs no complex cause. This is the cleanest floor for "self-organization."
Concrete real-world correspondences run in a string: the pattern on a cone snail's shell (the spacetime diagram of a 1D rule, its time axis frozen into calcium), the discrete version of reaction–diffusion patterns (Topic 13's Turing patterns), lattice models of forest fire and percolation (Topic 17), and abstractions of parallel computing and lattice gases. Its core falsifiable expectation: given a macroscopic pattern, if a simple local rule can reproduce it, the "complex design / central control" hypothesis is weakened; if nothing can, that in turn signals long-range coupling or a global constraint in the system.