About Cellular Automata | Game of Life, Rule 30, Rule 110 & More

The four basic parts

Every cellular automaton is built from the same four parts. The grid is the space the cells live in. It can be a one-dimensional line, a two-dimensional plane like a chessboard, or even a three-dimensional space. The states are what a cell can be. In the simplest case a cell is binary: black or white, 1 or 0. The neighborhood is the set of cells that directly affect a cell. On a square grid it is usually the Moore neighborhood, all eight surrounding cells, or the von Neumann neighborhood, only north, east, south, and west. The rules are the brain of the automaton: the logic that gives each cell its new state. For example: if I am alive but have fewer than two living neighbors, I die of loneliness. Every cell applies the same rules at the same moment.

1. Conway's Game of Life

Rules: B3/S23. A living cell survives with 2 or 3 living neighbors. A dead cell comes alive with exactly 3. Every other cell is dead in the next generation. John Conway designed it in 1970, and Martin Gardner's column in Scientific American made it famous. It produces gliders, oscillators, and spaceships. Bill Gosper found the first glider gun the same year: a pattern that fires a new glider every 30 generations, forever. Life can perform computation, since gliders can carry signals and collide like logic gates. Above all it shows complex behavior growing from simple rules.

Gosper glider gun in the Game of Life firing a diagonal stream of gliders — Gosper glider gun after 330 generations. Rendered in PictorX.

2. Rule 30

Type: a one-dimensional elementary cellular automaton. Each cell's next state depends on itself and its two neighbors, and every generation is drawn as a new row below the last. Stephen Wolfram introduced Rule 30 in 1983. Start from a single black cell and it grows a chaotic triangle. It appears random despite its deterministic rule, so random that its middle column has been used as a pseudorandom number generator. The same kind of triangles appear in the pigment of the Conus textile sea shell.

Rule 30 triangle grown from a single black cell, chaotic on the right and striped on the left — Rule 30 from one black cell, 224 generations. Rendered in PictorX.

3. Rule 110

Type: a one-dimensional elementary cellular automaton, like Rule 30, with a different table of eight answers. Rule 110 is proven to be computationally universal: Matthew Cook showed that with a suitable first row it can emulate any computation a general-purpose computer can carry out. It supports moving structures that travel across a repeating background and interact when they meet. Those collisions are what the proof uses as its logic. It demonstrates how very simple rules can emulate arbitrary computation.

Rule 110 grown from one cell on the right, spreading to the left in nested triangles — Rule 110 from one black cell on the right edge. Rendered in PictorX.

4. Brian's Brain

States: off, on (firing), and refractory. Rules: an off cell turns on if exactly 2 neighbors are on. An on cell becomes refractory. A refractory cell turns off. Brian Silverman designed it. Because a cell must rest for a generation after it fires, every pulse keeps moving away from where it has been. The result is a crowd of self-propelled patterns that resembles waves in excitable media, such as nerve tissue or heart muscle, and often looks alive and organic.

Brian's Brain spreading from a random patch, firing cells in yellow and fading trails in violet — Brian's Brain 70 generations after a random patch, with fading trails. Rendered in PictorX.

5. Wireworld

States: empty, electron head, electron tail, and conductor. Rules: a head becomes a tail, a tail becomes conductor, and a conductor becomes a head when exactly 1 or 2 of its neighbors are heads. Empty cells stay empty. Brian Silverman also designed Wireworld, in 1987. Conductor cells are wires, and a head followed by a tail is an electron running along them. It can simulate electronic circuits: a loop of wire with one electron is a clock, a small notch is a diode, and a few cells make a logic gate. Complete computers have been built inside it, such as the Wireworld computer by David Moore and Mark Owen, which calculates prime numbers.

Wireworld circuit with two clock loops, two diodes, and an XOR gate, electrons in blue and red on yellow wire — Two clocks, two diodes, and an XOR gate in Wireworld. Rendered in PictorX.

Wolfram's 256 rules and four classes

A one-dimensional cell with two neighbors sees one of eight patterns, from 111 down to 000. A rule gives the new state for each of them, so it is eight bits, and there are 2⁸ = 256 elementary rules. Read the eight answers as a binary number and you get the rule's name: Rule 30 is 00011110, and Rule 110 is 01101110. Stephen Wolfram sorted the rules by what they do, from order to chaos. 1. Class 1 settles into a uniform state. 2. Class 2 settles into stable or repeating structures. 3. Class 3 stays chaotic and random-looking, like Rule 30. 4. Class 4 builds structures that move and interact on the border between order and chaos, like Rule 110.

Difficulty ranking

Game of Life ★☆☆☆☆ · Rule 30 ★☆☆☆☆ · Brian's Brain ★★☆☆☆ · Wireworld ★★★★☆ · Rule 110 ★★★★★. The first two explain themselves as you watch. Rule 110 hides its moving structures in a repeating background.

Most beautiful visually

1. Brian's Brain · 2. Conway's Game of Life · 3. Rule 30 · 4. Rule 110 · 5. Wireworld.

Most important mathematically

1. Rule 110, for universality · 2. Game of Life, for universality and emergence · 3. Rule 30, for chaos and randomness · 4. Wireworld, for digital logic · 5. Brian's Brain, for excitable systems.

In nature, physics, and cryptography

Cellular automata are used to simulate complex systems in nature, physics, and cryptography. The idea goes back to Stanisław Ulam and John von Neumann in the 1940s, who used a grid of cells to design a machine that could copy itself. In the real world you can see cellular automata in the pigment of some shells, such as the Conus textile, whose triangles look like Rule 30, and in the scales of the ocellated lizard, which switch between green and black by a rule close to a cellular automaton. Physicists use them to model gas flow, sand piles, and forest fires. Rule 30's apparent randomness made it a candidate for random number generators and stream ciphers.

Explore it in PictorX

Open Cellular Automata to run all five. Watch the glider gun, a fleet of spaceships, or the R-pentomino, which takes 1,103 generations to settle. Type any Life rule such as B36/S23, or any elementary rule number from 0 to 255. Draw and erase cells, send electrons through the Wireworld circuits, wrap the edges, and switch to colorful mode. Save a PNG or open the canvas in the PictorX editor.

Frequently asked questions

What is a cellular automaton?

A grid of cells in which every cell has a state. At each tick all cells update together by one fixed rule that looks only at a cell and its neighbors. Despite the simple rules, the patterns can be complex and unpredictable.

Who invented cellular automata?

Stanisław Ulam and John von Neumann, in the 1940s at Los Alamos. John Conway's Game of Life (1970) made the idea popular, and Stephen Wolfram studied the 256 elementary rules in the 1980s.

Which cellular automata are Turing complete?

Among the five here, Rule 110 and the Game of Life are proven universal, and Wireworld can hold a complete computer. Universal means that, with the right starting pattern, they can carry out any computation a general-purpose computer can.

What are Wolfram's four classes?

Class 1 dies into a uniform state, class 2 settles into stable or repeating structures, class 3 stays chaotic like Rule 30, and class 4 builds moving, interacting structures like Rule 110.

Why does Rule 30 look random?

Every step is fixed, but each cell mixes its left neighbor with the other two in a way that spreads small differences quickly. No simple pattern has been found in its middle column, which is why it has been used to make random numbers.