The simplest universal computer
A popular account of Wolfram's 2,3 machine and Alex Smith's 2007 proof. Based on: The Prize Is Won; The Simplest Universal Turing Machine Is Proved—Stephen Wolfram Writings.
The $25,000 question
In May 2007, Stephen Wolfram — physicist, software entrepreneur, and author of the 1,200-page tome A New Kind of Science (2002) — put a $25,000 bounty on a single yes-or-no question: is one particular, absurdly simple little machine capable of universal computation — that is, capable of computing anything that any computer, present or future, can compute?
Forty-seven days later, a 20-year-old undergraduate from Birmingham, Alex Smith, emailed in a 40-page proof. After a couple of rounds of revision and scrutiny by a prize committee, the answer was announced in October 2007: yes. The simplest candidate computer anyone had ever seriously proposed really can do everything. The ceremony was held, fittingly, at Bletchley Park — where Alan Turing, who invented the whole concept, had worked during the war.
To appreciate what was proved, you need three ideas, none of which requires any mathematics: what a Turing machine is, what a cellular automaton is, and what "universal" means.
What "universal" means
In 1936, before any electronic computer existed, Alan Turing imagined a machine so stripped-down that you could reason about it perfectly, yet so general that it could perform any computation whatsoever. The astonishing discovery of that era (made independently by Turing, Church, and others) is that such a ceiling exists at all: there is a single, fixed notion of "computable," and a machine that reaches it — a universal machine — can imitate any other machine, given the right instructions.
Your laptop is a universal machine. So is your phone. That's why software is possible: you don't buy a new physical device for every new task; you feed one general-purpose device a new description of the task. A universal machine simulating another machine is exactly what happens when a Windows game runs on Linux through a translation layer — it's just that universality guarantees this works for any machine and any task, given enough time and memory.
The practical question Wolfram spent decades on: how simple can a universal machine be? Our engineering intuition says universal computers need millions of carefully arranged parts. The answer that emerged is almost comical: six instructions.
Turing machines: a clerk on an infinite strip of paper
A Turing machine is usually pictured as a clerk working along an endless strip of paper divided into squares:
- Each square carries a color (you can think of them as symbols, like 0, 1, 2). A machine with "3 colors" has three possible marks per square.
- The clerk (the head) sits on one square at a time and is in one of a fixed number of states — moods, if you like. A "2-state" machine's clerk has just two moods.
- The machine is a fixed list of rules, one for every (state, color-under-the-head) combination. Each rule says: what color to write on this square, whether to step left or right, and what state to be in next.
That's the whole machine. A 2-state, 3-color machine ("2,3" for short) needs exactly 2 × 3 = 6 rules. Each rule has 2 × 2 × 3 = 12 possible fillings (2 states to go to, 2 directions, 3 colors to write), so there are 12⁶ = 2,985,984 possible 2,3 machines — a haystack small enough for a computer to search exhaustively. Wolfram did.
A "program" for such a machine is just the initial pattern of colors on the strip (the input), plus where the head starts. The machine then clatters away: read, write, move, repeat.
Cellular automata: a chorus instead of a soloist
A cellular automaton is the other famous species of ultra-simple computer, and it differs from a Turing machine in one poetic respect: nobody moves, and everybody acts at once.
Imagine a single row of squares stretching off in both directions, each square black or white. Time proceeds in ticks. At every tick, every square simultaneously looks at itself and its two immediate neighbors, consults the same little table, and repaints itself accordingly. The entire machine is the table — 8 entries, one for each possible three-square neighborhood.
The most famous example is rule 110, discovered to be special by Wolfram in the 1980s. Its complete table:
Neighborhood | 111 | 110 | 101 | 100 | 011 | 010 | 001 | 000 | Center becomes | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 0 |
(1 = black, 0 = white. Read the bottom row as the binary number 01101110 and you get 110 — hence the name. All 256 such "elementary" rules are numbered this way.)
Start rule 110 from a single black square and let it run. What you get is not order and not chaos but something eerily in between: a repeating crystalline wallpaper (nicknamed the ether) crisscrossed by persistent little structures — gliders — that drift at various speeds and, when they collide, produce other structures in a rich bestiary of interactions. Watching a spacetime diagram of rule 110 (each new row is the next tick) looks like watching particles in a bubble chamber.
In the 1990s Matthew Cook, working with Wolfram, proved something remarkable: by choosing the initial pattern cleverly, you can arrange rule 110's gliders and their collisions to implement any cyclic tag system — a simple kind of rewriting machine (imagine a row of bits whose leftmost bit is deleted each step, with new bits appended at the right end according to a rotating list of little programs) that was already known to be universal. So rule 110, a table you can memorize in a minute, is a universal computer. The proof appeared in A New Kind of Science.
Keep rule 110 in mind. It becomes the key witness in the trial of the 2,3 machine.
The race to the bottom
Turing's original 1936 universal machine took four pages of dense notation to describe. Once the concept existed, a sport emerged: find the smallest universal machine, measured by states and colors.
- 1956: Claude Shannon systematically studied the question and showed you can trade states for colors (many colors, few states, or vice versa).
- 1962: Marvin Minsky built a 7-state, 4-color universal machine — the record for forty years.
- 1980s–90s: Yurii Rogozhin and others found a family of small machines exploiting the trade-off: 4 states and 6 colors, 3 states and 9 colors, 2 states and 18 colors, and so on. But nobody got down to 2 or 3 colors with only 2 or 3 states.
- 2002: In A New Kind of Science, Wolfram exhibited a 2-state, 5-color universal machine. And he noted that no 2-state, 2-color machine can ever be universal (that much is provable — their behavior is too simple). So the frontier, the very edge of possibility, was 2 states and 3 colors.
Out of the 2,985,984 possible 2,3 machines, Wolfram's searching had turned up one candidate whose behavior looked complex enough that his intuition — and his grand hypothesis, the Principle of Computational Equivalence (about which more below) — said it should be universal. On page 709 of the book he wrote that proving it "will no doubt be very difficult," but that he suspected it was true. The 2007 prize put money behind the hunch.
The machine itself
Here it is — the entire computer. Two states, A and B; three colors, 0, 1, 2; six rules:
| State | Reads | Writes | Moves | Becomes | | A | 0 | 1 | right | B | | A | 1 | 2 | left | A | | A | 2 | 1 | left | A | | B | 0 | 2 | left | A | | B | 1 | 2 | right | B | | B | 2 | 0 | right | A |
That table is not a description of the machine. It is the machine. You could engrave it on a coin.
To see it breathe, start the head on a blank (all-0) strip, in state A, and follow along:
- A reads 0 → writes 1, steps right, becomes B. (strip: 1)
- B reads 0 → writes 2, steps left, becomes A. (strip: 1 2)
- A reads 1 (the square from step 1) → writes 2, steps left, stays A. (strip: 2 2)
- A reads 0 (fresh territory) → writes 1, steps right, becomes B. (strip: 1 2 2)
- B reads 2 → writes 0, steps right, becomes A. (strip: 1 0 2)
- A reads 2 → writes 1, steps left, stays A. (strip: 1 0 1)
…and so on, forever. Six rules, three symbols, two moods, clattering back and forth.
There's a lovely way to see this machine as a bridge between our two species of simple computer. A cellular automaton is a row of cells where every cell updates in lockstep. A Turing machine is what you get when only one cell — the one under the head — is allowed to change, and the privilege of changing is itself passed around like a torch. It is, in effect, a cellular automaton with a single wandering active cell: a chorus reduced to a soloist. (You can even draw its history the same way — stack successive snapshots of the strip, mark the head, and you get a spacetime picture just like rule 110's, with the head tracing a jagged path through it.) The 2007 theorem says this lonely automaton is already enough.
Watching it run
Why did Wolfram suspect this particular machine? Because of what it does when you simply run it — the NKS methodology of doing experiments on tiny programs. From simple initial patterns, the 2,3 machine's behavior is a tease: sometimes it settles quickly into repetition or simple nesting; sometimes it races for hundreds or thousands of steps in fits of apparent complexity before revealing structure; and from some starting patterns it churns out irregular, ever-changing detail with no sign of ever settling down. It behaves, in other words, exactly like rule 110 and the other known universal systems: alive.
Wolfram's Principle of Computational Equivalence (PCE) is the sweeping conjecture that this appearance is decisive: whenever a simple system's behavior isn't obviously simple, the computation it's performing is essentially always maximally sophisticated — universal. Computation, on this view, isn't a ladder you climb by adding complexity; there's a low threshold, and above it everything is equivalent. The 2,3 machine, sitting at 2 states and 3 colors with visibly non-simple behavior, was a crisp, testable prediction of PCE: either the threshold really is that low, or the principle is wrong.
The proof
Alex Smith, an undergraduate in electronic and computer engineering with a self-described background in "mathematics and esoteric programming languages," took up the puzzle — initially, he later said, expecting to prove the machine was not universal. Instead he found "little bits of behavior that were more complicated," and out of those bits he built the proof.
The strategy is a relay race of simulation, each leg already known except the first:
- The 2,3 machine can emulate rule 110. This is Smith's contribution: a way to encode a rule-110 evolution onto the Turing machine's strip so that the six rules, dutifully clicking away, reproduce it. He effectively wrote a compiler — a translator from programs for the cellular automaton into initial patterns for the Turing machine.
- Rule 110 can emulate any cyclic tag system. (Cook's theorem.)
- Cyclic tag systems are universal — they can emulate any Turing machine, hence any computation.
Chain the three and the little machine inherits universality. The committee's questions sharpened the details; one member wanted the result checked against the formal definition of universality he himself had laid down in a seminal paper in 1956. After revisions, the proof stood, and the prize was awarded in October 2007.
Two honest caveats, both interesting:
- The compiler is terrible. Smith's encoding is astronomically large and horrendously inefficient for anything but toy programs. Nobody will run software on this machine. The result is one of principle, not practice.
- The fine print about the starting tape. Classical definitions of universality demanded a finite initial pattern and a machine that eventually halts with an answer. The 2,3 machine, like rule 110 before it (and like real computers, and like nature), never halts — and Smith's construction needs the strip pre-filled with an infinite, endlessly repeating background pattern, modified in a finite region to encode the program. Is that cheating? The crucial point, Wolfram argued, is that the infinite background is itself set up by a simple, definitely non-universal procedure — so when universal computation shows up, it's genuinely being done by the six rules, not smuggled in by the preparation. This relaxed notion ("weak universality" in the technical literature) is the same one under which rule 110's universality was established. The committee was convinced.
Why it matters
The immediate significance is a monument placed at the exact edge of the possible: 2 colors and 2 states provably cannot be universal; 2 states and 3 colors can. The simplest conceivable Turing machine territory is now fully mapped.
The deeper significance is what Wolfram was really testing. PCE predicts that universality is cheap and common — that nature stumbles into universal computation constantly, and that the elaborate engineering of our own computers is a historical accident rather than a necessity. The 2,3 machine is Exhibit A: nobody designed it; Wolfram just searched a small space of possibilities and fished out a universal computer the way you'd fish a interesting stone off a beach.
That flips a deep intuition on its head, and it suggests a different kind of technology. Wolfram mused about molecular computers built like the 2,3 machine itself: "tapes a bit like RNA strands, and heads moving up and down like ribosomes." If universal computation takes only six rules, then to compute at the nanoscale you don't need to miniaturize a CPU — you need to find a molecule-scale system already doing something equivalent and program it. Nature, which runs cells with ribosomes reading tapes, may have been there all along.
And there's a final, pleasing symmetry to the story. The proof that the simplest Turing machine is universal runs through a cellular automaton: the soloist was certified by showing it can conduct the chorus. The two simplest kinds of computer ever conceived turn out to stand at the same threshold — the threshold above which everything that can be computed, can be computed by anything.