Quartz 4

Cellular Automata — How Simple Rules Create Universes

8 min read

Cellular Automata — How Simple Rules Create Universes

A cellular automaton (CA) is the simplest possible model of computation: a grid of cells, each in one of a finite number of states (often just 0 or 1), that updates every tick according to a fixed local rule. The rule is usually: look at a cell and its immediate neighbors, apply a table, produce the next state. No global controller. No long-range communication. Pure local logic, applied everywhere at once.

From this poverty of means, something extraordinary emerges: universes with their own physics, self-reproducing organisms, unsolvable problems, and patterns that mirror the complexity of life itself.

Confidence level: established (CA behavior) | emerging (physics-of-reality interpretation)

Conway’s Game of Life (1970)

John Horton Conway defined his cellular automaton in 1970 with four rules on a 2D grid of square cells, each alive or dead:

  1. Underpopulation: A live cell with fewer than 2 live neighbors dies
  2. Survival: A live cell with 2 or 3 live neighbors lives on
  3. Overpopulation: A live cell with more than 3 live neighbors dies
  4. Birth: A dead cell with exactly 3 live neighbors becomes alive

These 4 rules — simpler than any known organism’s gene expression — generate a universe of unbounded complexity. Still lifes (stable patterns), oscillators (repeating patterns), and spaceships (self-perpetuating structures that translate across the grid) emerge. The most famous spaceship, the glider, travels diagonally across the grid indefinitely, carrying information.

Conway’s original motivation was explicit: design a “universal” automaton — one capable of simulating any computation. He succeeded beyond expectations.

The Four Classes of Behavior (Wolfram, 1983)

Stephen Wolfram systematically studied all 256 possible 1D elementary cellular automata — rules that look at a cell and its two neighbors — and discovered that behavior falls into exactly four classes:

ClassBehaviorExample
IAll cells die or converge to homogeneityRule 0
IISimple stable or periodic patternsRule 4
IIIChaotic, apparently randomRule 30
IVComplex, persistent structures — edge of chaosRule 110, Game of Life

Class IV is the gold. It sits at the phase transition between order (Class II) and chaos (Class III) — what Langton called the edge of chaos. This is the computational sweet spot: complex enough to carry information indefinitely, ordered enough that structures persist long enough to interact.

Rule 30, a Class III automaton, appears so random that Wolfram used it as Mathematica’s default pseudorandom number generator for decades.

Universal Computation in 4 Rules

By the 1980s it was conjectured that Life is Turing complete — capable of simulating any computation that any computer can perform. This was definitively proved in the 2000s when constructions appeared in Life for: logical gates (AND, OR, NOT), memory (glider gun streams as registers), counters, and finally entire computer architectures. Life contains a universal computer. Given the right starting configuration and enough space, Life’s 4 rules compute anything computable.

The implications are philosophically vertiginous. If Life runs on a sufficiently large grid with a specific starting pattern, it could simulate:

  • Every weather forecast ever computed
  • Every chess game ever played
  • This very sentence being generated

Rule 110: The Simplest Known Universal Computer

Conway’s Life is 2D. Wolfram found something more radical: Rule 110, a 1D automaton with only 8 rule cases (two neighbors + cell = 8 possibilities), is also Turing complete. Matthew Cook proved this in 1994 (published 2004), showing Rule 110 could emulate a cyclic tag system, which is known universal.

Rule 110 is widely believed to be the simplest possible universal computation system in nature. It has three inputs, one output, and yet embeds the full power of modern computing.

This points at a deep principle: the complexity of the output depends almost entirely on the initial conditions, not on the complexity of the rule. A 3-input rule and a 4-rule automaton can produce identical computational power as a billion-transistor chip. The computability is a property of the dynamic, not the mechanism.

Wolfram’s Bigger Claim: Computation as Physics (2002, 2020)

In A New Kind of Science (2002) and more formally in the Wolfram Physics Project (2020–present), Stephen Wolfram proposed the inverse of the above insight: if computation can produce physics-like complexity, perhaps physics is computation.

The Wolfram Physics Project models space and time as a hypergraph whose nodes represent tokens of space and whose edges represent relations between them. The universe evolves by applying local rewriting rules to this hypergraph — a generalized cellular automaton over a non-grid geometry. From these rules, Wolfram’s team has derived:

  • Special relativity (from causal invariance of the rewriting)
  • General relativity (from volume growth rules for geodesics)
  • Quantum mechanics (from the branching of equivalent rewriting paths)

Whether this program succeeds as physics remains contested. But the structural claim — that physics is an instance of computation, not merely describable by it — is a profound reframing.

2024–2025: New Discoveries

New Glider Gun (2024)

A glider gun with period 15 was discovered in Life in 2024 — 54 years after the original period-30 Gosper Glider Gun was found. The new gun is built from components that were separately known for 30 years but whose combination hadn’t been tried. This illustrates the vast unexplored configuration space of Life: simple structures, hiding in plain sight.

Self-Replicating Patterns From Random Initial Conditions (May 2025)

A study in Physical Review E (2025) reported an algorithm for searching Life-like rules that enable small structures to self-replicate spontaneously from random initial conditions — not from hand-crafted seeds. This is a qualitative shift: prior self-replicators in Life required enormous engineered starting configurations. Finding replicators that emerge from disorder makes Life-like systems genuine origin-of-life analog systems.

Continuous Game of Life: Cell Division and Motility (ALIFE 2025)

A minimal continuous variant of Life (using continuous cell state values and partial differential equations rather than discrete rules) generates cell-like patterns that spontaneously self-replicate, glide, and disappear — mimicking the three key behaviors of biological cells. The system maps onto a reaction-diffusion equation with morphogen concentrations, bridging the gap between cellular automata and developmental biology.

LifeGPT: Transformers Learn Life (npj Artificial Intelligence, 2025)

Researchers trained a decoder-only GPT-style transformer model to compute Life transitions. LifeGPT achieves near-perfect accuracy on Life state predictions without being given grid dimensions or boundary conditions — it infers the topology from context. This demonstrates that transformer attention heads can learn local spatial computation rules, raising the question of whether transformers implicitly implement CA-like dynamics in language tasks.

25-Year Anniversary of Evoloops (2024)

The 25th anniversary review of evoloops — an evolutionary variant of self-reproducing loops in CA — established that Darwinian evolution by variation and natural selection is possible within deterministic cellular automata. The recent “open-ended evolution” movement in artificial life traces its foundations to this 1999 result.

The Abiogenesis Parallel

The continuous Game of Life finding (ALIFE 2025) makes explicit what has been implicit since von Neumann’s 1948 self-reproducing automaton: cellular automata provide a minimal model for the origin of life.

Life requires, at minimum:

  1. A pattern that persists against noise (stability)
  2. A pattern that can copy itself (replication)
  3. Variation in copies (mutation)
  4. Selection based on differential persistence (evolution)

All four have now been demonstrated in CA systems without designer intervention. The self-replication emerges from the rule. The variation comes from random errors in the initial conditions. The selection follows automatically from which patterns survive longer.

This doesn’t prove life did emerge from CA-like dynamics on early Earth. But it establishes that no “special ingredient” — no divine hand, no vitalism — is required beyond local physical rules operating on matter in a grid.

Undecidable Properties

A striking connection to the concept-halting-problem: many properties of cellular automata are formally undecidable. Given a Life starting configuration, you cannot generally determine by any algorithm whether:

  • It will eventually die out
  • It will produce a glider
  • It will reach a periodic state
  • It contains a specific subpattern after n steps

This is not a failure of current methods — it is a theorem. Life is universal enough that questions about its long-term behavior map onto arbitrary Turing machine halting problems. The computational richness that makes Life interesting makes it permanently opaque in general.

Key Facts

  • Conway’s Game of Life: 4 rules, 2D grid, proved Turing complete (2000s)
  • Rule 110: 1D, 8 rule cases, simplest known Turing-complete system
  • Wolfram’s 4 classes: I (die), II (stable), III (chaotic), IV (complex, edge of chaos)
  • Rule 30: Class III, random-appearing; used as Mathematica’s PRNG
  • 2024: new period-15 glider gun discovered in Life, 54 years after first
  • May 2025 Physical Review E: self-replicating patterns emerging spontaneously from random initial conditions in Life-like rules
  • ALIFE 2025: continuous Life generates self-replicating, motile cell-like patterns
  • LifeGPT (npj AI, 2025): transformer model learns Life transitions without rule specification
  • Wolfram Physics Project: proposes spacetime is a hypergraph with CA-like rewriting rules

See Also

Graph View

Backlinks