An eight-line rule
Rule 110 is one of the elementary cellular automata: a single row of cells, each either 0 or 1, that updates in lockstep. The new value of a cell depends on three things only: the cell to its left, the cell itself and the cell to its right. Three bits have eight possible combinations, so the entire rule is a table with eight entries.
The name 110 comes from reading the outputs as a binary number. In the standard numbering, the eight neighborhoods are listed from 111 down to 000, and the outputs are as follows.
| Left, center, right | New center |
|---|---|
| 111 | 0 |
| 110 | 1 |
| 101 | 1 |
| 100 | 0 |
| 011 | 1 |
| 010 | 1 |
| 001 | 1 |
| 000 | 0 |
Read the outputs as 01101110. In decimal that is 64 + 32 + 8 + 4 + 2, which is 110. That is where the name comes from.
One step by hand
Take the row 0 0 1 0 0 and treat cells outside as 0. For each cell, look at its three-cell neighborhood.
- First cell: neighborhood 0 0 0, so it becomes 0.
- Second cell: neighborhood 0 0 1, so it becomes 1.
- Third cell: neighborhood 0 1 0, so it becomes 1.
- Fourth cell: neighborhood 1 0 0, so it becomes 0.
- Fifth cell: neighborhood 0 0 0, so it becomes 0.
The new row is 0 1 1 0 0. The single on cell has grown one step to the left. Repeating this, a lone cell keeps spreading leftward and builds an irregular triangular texture. This asymmetry is a feature of the rule: it is not mirror-symmetric, and structures tend to drift in one direction.
Why people call it special
Rule 110 sits in an interesting spot. Some elementary rules are boring: they die out, freeze or repeat simply. Others look purely random. Rule 110 produces a mix, with regular background patterns and localized structures that move and interact against that background. These moving structures are often called gliders or particles.
The key result, usually credited to Matthew Cook, is that Rule 110 is capable of universal computation. The argument, in broad outline, is that gliders can be arranged to carry and combine signals, and that by choosing a suitable collection of them, one can simulate a cyclic tag system, which is itself known to be universal. Since tag systems can emulate a Turing machine, so can Rule 110. This is a real mathematical result, but the proof is long and technical, and I will not try to reproduce it here.
What universal means here
Universality is easy to over-read, so some caveats apply.
- Needs an unbounded row. The simulation uses an infinitely wide row, or at least one that can grow as needed. A fixed finite row has finite memory, closer to the idea of a finite automaton. This echoes the distinction between ideal and real machines.
- Needs a carefully built starting pattern. Most starting rows do nothing like computation. The program is encoded in a specific, large, regular-looking initial condition.
- It is very inefficient. Encoding even a short computation takes enormous numbers of cells and steps compared with a direct implementation. The result is about possibility, not speed.
- It does not make the rule useful for ordinary work. Nobody would choose it to write a program for practical reasons.
The bigger lesson
The significance is conceptual. It shows that universal behavior does not require a complex machine. A rule fitting on an index card, using a single row of bits, can in principle do anything a computer can. That shifts the question from how much machinery computation requires to how little, a theme shared with the search for small universal Turing machines and with minimalist esoteric designs.
It also has a flip side. If such a simple rule is universal, then predicting what it will do from a given start is, in general, as hard as the halting problem. There is no shortcut that tells you the final result without effectively running it. This property is sometimes called computational irreducibility, a term popularized by Stephen Wolfram, though how much weight it deserves outside this setting is a matter of discussion.
Related systems
Rule 110 is the usual one-dimensional example, with the Game of Life being the famous two-dimensional case. Each has its own style of building computers out of moving patterns. For general background on how automata can serve as programming systems, see the broader treatment of grids of cells. If you want to explore Rule 110 yourself, a few lines of code are enough: store a row of bits, compute the next row with the table above, and print it, then compare the output to hand-worked steps.