Emergence and implications

Emergence

Life is the cleanest example anyone has of emergence: behaviour at one level that is not visible in the description of the level below it. The rules are complete and exact - there is no hidden physics, no approximation, no noise. You could not know more about the system than you already do. And still, the statement "a glider moves diagonally at one cell every four generations" is not derivable from the rules by inspection. You have to run it.

This is uncomfortable for a strong reductionist position. Everything a glider does is the rules being applied - there is no extra force involved. But "glider" is nonetheless a genuinely useful, predictive, real concept that the rules do not contain. Daniel Dennett used Life extensively for precisely this reason: it demonstrates that higher-level descriptions can be indispensable without being spooky. You can be a complete reductionist about the physics and still need the word "glider" to say anything sensible about what is happening.

The Game of Life illustrates how the physical stance and the design stance can both be legitimate ways of describing the same events.

Daniel Dennett, on why Life keeps appearing in philosophy of mind

Undecidability

Because Life is Turing complete, all the classical limits of computation apply to it directly. In particular:

• There is no general algorithm that decides whether a given Life pattern will ever die out. That is the halting problem in a costume.
• There is no general algorithm that decides whether a given pattern will ever produce a particular other pattern.
• Determining whether a configuration has a predecessor - a "Garden of Eden" question - is decidable but NP-hard in general.

This is a deep point about determinism, and it is the one people usually get wrong. Life is perfectly deterministic: given the state now, the state at every future generation is fixed. It is also unpredictable in the strict sense that there is no shortcut - for most patterns the fastest way to find out what happens at generation ten million is to compute all ten million generations. Wolfram calls this computational irreducibility. Determinism does not imply predictability. Those are different claims, and Life separates them cleanly.

Gardens of Eden

Some configurations have no predecessor: they can be drawn, but they can never arise from any earlier generation. Their existence in Life was proved by Edward Moore and John Myhill in 1962 - before Life existed, as a general theorem about automata whose rules are not injective. The first explicit Life example was found in 1971; the smallest known ones are now down to a handful of cells across.

The Garden of Eden theorem has an elegant consequence: a cellular automaton has Gardens of Eden if and only if it has "twin" configurations that evolve identically. Irreversibility and unreachability are two faces of the same fact.

Biology and morphogenesis

Von Neumann's original motivation - self-reproduction - turned out to describe how biology actually works, and the family resemblance did not stop there. Local rules producing global pattern is exactly the problem of morphogenesis: how does a ball of identical cells become a body with a front and a back?

Alan Turing's 1952 paper on reaction-diffusion systems answered it in continuous mathematics; cellular automata answer it discretely. Both produce spots, stripes and spirals from uniform starting conditions with no blueprint anywhere. Real developmental biology uses both mechanisms. The pigmentation of Conus textile shells is a cellular automaton in the literal sense - the mantle lays down pigment based on the state of the adjacent tissue, one row at a time, producing patterns that match elementary automaton Rule 30.

Cellular automata are also used seriously to model excitable media (the spiral waves in cardiac fibrillation), forest fires and epidemics, tumour growth, traffic flow - the Nagel-Schreckenberg model reproduces phantom traffic jams from four local rules - and crystal growth, which is where Ulam started.

Computation inside Life

The engineering achievements inside Life are not toys. Because gliders can be emitted on demand, blocked, reflected and made to collide in controlled ways, they behave as signals. From that:

• AND, OR and NOT gates were demonstrated by the early 1970s, using glider streams as inputs and eaters and blocks as gates.
• Paul Rendell built a working Turing machine in Life in 2000, with an unbounded tape added in 2010.
• Adam P. Goucher's Spartan universal computer-constructor can build arbitrary patterns from a program tape - a genuine realisation of von Neumann's original goal inside Conway's minimal rule.
• In 2006 Brice Due built OTCA metapixel: a 2048×2048 Life pattern which behaves exactly like one cell of Life. Tile the plane with it and you are running Life inside Life, at a slowdown of 35,328 generations per meta-generation. The construction is fully recursive.
• In 2013 a distributed search finally produced a replicator in Life itself - Gemini and later the "linear propagator" - patterns that build copies of themselves, closing the loop back to 1948.

Digital physics

If a two-state grid with four rules can support universal computation, self- reproduction and unbounded complexity, the obvious question follows: is the universe doing something similar?

Konrad Zuse asked it first, in Rechnender Raum (Calculating Space, 1969), proposing that the universe is the output of a deterministic cellular automaton. Edward Fredkin developed the idea into "digital philosophy". Stephen Wolfram devoted much of A New Kind of Science (2002) to the claim that simple programs, not equations, are the right language for physics; his more recent Wolfram Physics Project works with rewriting rules on hypergraphs rather than fixed lattices.

The idea has serious problems. A fixed lattice picks out a preferred frame of reference, which special relativity forbids; Bell's theorem constrains local hidden variable models severely; and no digital physics programme has yet produced a testable prediction that differs from established theory. It remains an intriguing research programme rather than a result. But it is not silly, and Life is the reason people take it seriously enough to argue about.

Determinism and free will

Life is a favourite thought experiment in the free will debate because it removes every distraction. A pattern in Life does things - it moves, it reacts, it can even compute - and every one of those actions is fully determined by the previous generation. If you built a mind out of gliders, would it be free?

Compatibilists say the question is confused: freedom is about whether your actions flow from your own deliberation, not whether they are caused. A Life computer deliberating and a Life computer being pushed around are genuinely different arrangements, and the difference is the one that matters. Incompatibilists reply that "your own deliberation" is itself just more determined machinery.

Conway himself came at this from an entirely different angle. With Simon Kochen he proved the Free Will Theorem (2006), which shows that if experimenters have a certain kind of freedom in choosing measurement settings, then elementary particles must have an analogous freedom - their response is not a function of any prior information in the universe. It is a statement about indeterminacy in quantum mechanics rather than about Life, but Conway plainly enjoyed the fact that the man famous for a deterministic universe had co-authored a theorem about freedom.

Culture

The glider was adopted in 2003 as an emblem for the hacker community, proposed by Eric S. Raymond on the grounds that it is the first thing anyone discovers in Life, and that it stands for something that emerges rather than being designed. It has since appeared on badges, tattoos, album covers and at least one gravestone.

Life has been used to generate music, drive generative art, teach programming for fifty years, and serve as a benchmark for parallel computing. Its appearance in Scientific American in October 1970 is credited with burning a considerable amount of institutional computer time in the years that followed - Conway himself later estimated that the game must have wasted millions of dollars in mainframe hours.