Cellular Automata Explained: Game of Life, Rule 30 and Rule 110, With a Simulator You Can Run

In October 1970, Martin Gardner’s “Mathematical Games” column in Scientific American introduced a solitaire game with three rules, no players and no way to win. John Conway, then at Cambridge, called it Life. He also put $50 on the table for anyone who could show that a finite pattern on the grid could grow without limit, and he wanted an answer before the year was out. The bet lasted one month. The rules, the wager and what happened next are the reason cellular automata are still taught, built and argued about more than fifty years later, and the simulator embedded in this article runs every one of the systems described below.

Video: Numberphile, “Inventing Game of Life (John Conway)”

What a cellular automaton is

A grid, a clock and one rule applied everywhere at once

Melanie Mitchell’s review of the field describes cellular automata as “decentralized spatially extended systems consisting of large numbers of simple identical components”. Strip the vocabulary away and three parts remain. There is a lattice of cells, each in one of a small number of states. There is a neighbourhood, the handful of cells each one can see. And there is a transition rule that reads a cell’s neighbourhood and returns its next state. Every cell applies the same rule at the same tick of a global clock, and the whole grid steps forward together.

Nothing in that description mentions computation, biology or chaos. Those arrive on their own.

The idea predates Conway by two decades. Stanislaw Ulam suggested the lattice framework to John von Neumann, who was chasing a specific question: “What kind of logical organization is sufficient for an automaton to be able to reproduce itself?” Von Neumann’s answer used 29 states per cell and a five-cell neighbourhood, and it was unfinished when he died in 1957. Arthur Burks completed the manuscript and published it in 1966 as Theory of Self-Reproducing Automata. Later researchers cut the state count to eight, then four. Conway cut it to two.

The rules of Conway’s Game of Life

Born with three, survive with two or three, otherwise dead

Life uses a two-state grid (alive or dead) and the Moore neighbourhood, the eight cells touching a given cell by edge or corner. The rule fits in a line of shorthand: B3/S23. A dead cell with exactly three live neighbours is born. A live cell with two or three live neighbours survives. Every other cell is dead on the next tick, whether from loneliness or overcrowding.

That notation matters beyond Life. B lists the neighbour counts that bring a dead cell to life and S lists the counts that let a live one survive. Since each of the nine possible counts can be in or out of each list, there are 2^18, or 262,144, “Life-like” rules sharing the same grid and neighbourhood. Conway began experimenting with two-dimensional rules in 1968, tracking patterns by hand with the black and white stones of a Go board, and settled on the one set where simple starting patterns would grow and change for a long time before settling.

The simulator above opens on a random Life soup. Press Clear, draw a few cells with the mouse, and step through one generation at a time to watch the rule do its work. A single cell dies at once. Three in a row flip between horizontal and vertical forever: the blinker, the smallest oscillator. A 2×2 block never changes.

The glider, the gun and the $50

Conway’s conjecture was that no finite pattern could grow forever; everything would die out, settle or oscillate. A team at MIT led by Bill Gosper disproved it in November 1970 with a pattern that fires a glider every 30 generations, the first of them on generation 15. Each glider travels diagonally across the grid, bounded by the rule’s own speed limit: no information can cross the grid faster than one cell per tick, which Life’s literature calls the speed of light. The population grows without bound. Gosper collected the $50 from Conway.

Select “Gosper glider gun” from the Pattern menu, or load it directly:

A gun is more than a curiosity. Gliders can be aimed, collided and annihilated, which means they can carry bits and perform logic. Life “has the power of a universal Turing machine”: anything a computer can calculate, a large enough Life grid can calculate too, and a universal constructor can be built inside it that contains a Turing-complete computer. That is a heavy result for a system whose entire specification is three sentences long.

Beyond Life: four rules that behave differently

Changing one digit in B/S changes the universe

The simulator carries five other two-dimensional rules, each a small edit to Life’s notation.

HighLife (B36/S23) adds birth on six neighbours. Most patterns behave as in Life, but the rule contains a small self-replicating pattern, something Life has only in enormous engineered constructions.

Day & Night (B3678/S34678) is symmetric under swapping live and dead cells: a pattern of dead cells on a live background evolves exactly like its inverse. Random soups form continents and seas that erode at the coastlines.

Seeds (B2/S) has an empty survival list, so every live cell dies after one tick. Birth on exactly two neighbours is all that keeps anything going, and most starting patterns produce “explosive chaotic growth.” Try drawing two adjacent cells.

Maze (B3/S12345) lets cells survive with anything from one to five neighbours. Growth freezes into corridors and walls that look drawn by a maze generator, because in effect they were.

Brian’s Brain, devised by Brian Silverman, adds a third state. A cell is off, on, or dying. An off cell turns on when exactly two of its neighbours are on; an on cell always passes to dying; a dying cell always turns off. The refractory step is borrowed from neurons, and the effect is that “almost every pattern in Brian’s Brain is a spaceship”. Patterns do not sit still. They stream.

One dimension, 256 rules

Wolfram’s elementary automata and the numbering behind them

Drop from two dimensions to one and the system becomes small enough to enumerate completely. An elementary cellular automaton is a row of cells, each alive or dead, where a cell’s next state depends only on itself and its immediate left and right neighbours. Three binary inputs give eight possible neighbourhoods. A rule assigns an output of 0 or 1 to each of the eight, so there are 2^8, or 256, rules in total. Read the eight outputs as a binary number and the rule gets a name.

In the simulator, choose “Elementary rule” and the grid becomes a time chart: the top row is the present, each row below is the next generation, and the picture scrolls once it reaches the bottom. On wide screens, a row of eight bit toggles appears next to the rule number so a rule can be edited directly.

Stephen Wolfram introduced the numbering, and he introduced Rule 30 in 1983 in a paper titled “Statistical mechanics of cellular automata.” Its binary form is 00011110. Started from a single live cell, Rule 30 grows a triangle whose left edge is orderly and whose interior is, for every statistical test anyone has applied, random. Wolfram used it to generate random integers in Mathematica for years. A pattern resembling it appears on the shell of the cone snail Conus textile, and the panels on the facade of Cambridge North railway station are drawn from its evolution.

Rule 110 and the proof Wolfram tried to stop

Rule 110 (binary 01101110) sits at the other extreme of interest. Its patterns are “neither completely stable nor completely chaotic”; localized structures travel across a periodic background and interact when they meet. Wolfram conjectured in 1985 that these collisions were enough to compute with. Matthew Cook, then working for Wolfram Research, proved it, presenting the result at a Santa Fe Institute conference in 1998. Wolfram Research claimed the talk breached Cook’s nondisclosure agreement and obtained a court order excluding the paper from the conference proceedings. The proof finally appeared in Complex Systems in 2004, and Rule 110 is now described as one of the simplest known Turing-complete systems. Among the 88 inequivalent elementary rules, it remains the only one where universality has been proven directly.

Set the rule number to 90 for a Sierpinski triangle, 184 for a one-lane traffic model where cells are cars, or 184’s neighbours to see how fragile the traffic analogy is.

Order, chaos and the class in between

Wolfram’s four classes, and why class 4 is the interesting one

In 1984 Wolfram sorted cellular automata into four qualitative classes. Class 1 rules relax to a fixed, uniform state from almost any start. Class 2 rules settle into fixed or periodic structures that depend on the initial configuration. Class 3 rules produce chaos; Rule 30 is the standard example. Class 4 is the odd category: “some initial configurations result in complex localized structures, sometimes long-lived.” Life and Rule 110 live here.

Mitchell’s review adds a caution that gets lost in retellings: “The membership requirements for class 4 are not rigorous.” The classification is a description of what the pictures look like, not a theorem, and the boundary between classes 3 and 4 is where most of the open questions in the field sit. Computation seems to need a system that can hold information (order) and move it around (disorder) at the same time. Rules that do both are rare, and nobody has a formula for predicting which rules will.

That tension connects to a question x9m8 covered from the machine-learning side in Emergent Abilities in Large Language Models: Real or a Mirage? Cellular automata are the cleanest place to study how qualitatively new behaviour can appear from a rule that was never changed.

Conway, Life and what he preferred to be known for

The inventor outlived by his least favourite invention

Conway died on April 11, 2020 at 82, from complications of COVID-19, having spent the latter part of his career as the John von Neumann Professor in Applied and Computational Mathematics at Princeton. His friend Peter Doyle told the university: “People invariably describe Conway as the inventor of the Game of Life.” Conway’s own stated proudest achievement was the surreal numbers, and his work on group theory, knot theory and sphere packing fills shelves that Life does not. The Numberphile video at the top of this article shows him telling the story of the game himself; its companion, Does John Conway hate his Game of Life?, answers the question in the title.

The book that carried Life to a wide audience after Gardner’s column was William Poundstone’s The Recursive Universe, first published in 1984 and still in print from Dover. Kirkus described Life in its review as “a completely programmable game that produces changing patterns on a visual display”, which was true in 1984 and is the reason the simulator here exists. Poundstone uses the game as a route into information theory, entropy and the limits of what science can predict, and it remains the most readable account of why a three-rule game kept physicists up at night.

Running the simulator

Controls, shortcuts and what to try

The simulator is a single page hosted at apps.x9m8.com/cellular-automata and the source is on GitHub. Draw cells with the mouse or a finger. Space plays and pauses, the right arrow steps one generation, R fills the grid at random, C clears it. The Cell slider changes resolution, the Speed slider sets generations per second, and “wrap edges” turns the grid into a torus so gliders leaving one side return on the other. Turn on “trails” in any two-dimensional rule to see where cells recently died.

A few experiments worth the time:

• Load the R-pentomino, five cells that take 1,103 generations to stabilize in Life. Watch how much of the grid it touches.
• Put the same random soup into Life, HighLife and Day & Night and compare how long each takes to stabilize.
• In Seeds, draw a single pair of cells and count the generations until the grid fills.
• Switch to the elementary rules, start from the centre cell, and walk the rule number up from 0. Classes 1 through 4 all appear before 256.

Every embed in this article is the same app with different starting parameters, which can be set in the URL: rule, pattern, elementary rule number, speed, cell size, wrap and autoplay. Anyone can link to a specific starting state.

Sources

• Martin Gardner’s October 1970 column and the rules of Life: LifeWiki, Conway’s Game of Life
• Gosper glider gun and the $50 prize: Wikipedia, Gun (cellular automaton)
• B/S notation, HighLife, Day & Night, Seeds and the count of Life-like rules: Wikipedia, Life-like cellular automaton; Highlife (cellular automaton); Seeds (cellular automaton)
• Brian’s Brain: Wikipedia, Brian’s Brain
• Von Neumann’s 29-state automaton: Wikipedia, Von Neumann cellular automaton
• Definition, origins and Wolfram’s four classes: Melanie Mitchell, “Computation in Cellular Automata: A Selected Review” (PDF)
• Rule 30: Wikipedia, Rule 30
• Rule 110 and Cook’s proof: Wikipedia, Rule 110
• R-pentomino, speed of light, Go board, Turing completeness: Wikipedia, Conway’s Game of Life
• Conway’s death and career: Princeton University, April 14, 2020
• The Recursive Universe review: Kirkus Reviews
• Videos: Numberphile, Inventing Game of Life; Numberphile, Does John Conway hate his Game of Life?