(Main prize page: The Wolfram 2,3 Turing Machine Research Prize)

“And although it will no doubt be very difficult to prove, it seems likely that this Turing machine will in the end turn out to be universal.”

So I wrote on page 709 of A New Kind of Science (NKS).

I had searched the computational universe for the simplest possible universal Turing machine. And I had found a candidate—that my intuition told me was likely to be universal. But I was not sure.

And so as part of commemorating the fifth anniversary of A New Kind of Science on May 14 this year, we announced a $25,000 prize for determining whether or not that Turing machine is in fact universal.

I had no idea how long it would take before the prize was won. A month? A year? A decade? A century? Perhaps the question was even formally undecidable (say from the usual axioms of mathematics).

But today I am thrilled to be able to announce that after only five months the prize is won—and we have the answer: the Turing machine is in fact universal!

Alex Smith—a 20-year-old undergraduate from Birmingham, UK—has produced a 40-page proof.

I’m pleased that my intuition was correct. But more importantly, we now have another piece of evidence for the very general Principle of Computational Equivalence (PCE) that I introduced in A New Kind of Science.

We are also at the end of a quest that has spanned more than half a century to find the very simplest universal Turing machine.

Here it is. Just two states and three colors. And able to do any computation that can be done.

We’ve come a long way since Alan Turing’s original 1936 universal Turing machine—taking four pages of dense notation to describe.

There were some simpler universal Turing machines constructed in the mid-1900s—the record being a 7-state, 4-color machine from 1962.

That record stood for 40 years—until in 2002 I gave a 2,5 universal machine in A New Kind of Science.

We know that no 2,2 machine can be universal. So the simplest possibility is 2,3.

And from searching the 2,985,984 possible 2,3 machines, I found a candidate. Which as of today we know actually is universal.

From our everyday experience with computers, this seems pretty surprising. After all, we’re used to computers whose CPUs have been carefully engineered, with millions of gates.

It seems bizarre that we should be able to achieve universal computation with a machine as simple as the one above—that we can find just by doing a little searching in the space of possible machines.

But that’s the new intuition that we get from NKS. That in the computational universe, phenomena like universality are actually quite common—even among systems with very simple rules.

It’s just that in our normal efforts of engineering, we’ve been too constrained to see with such things.

From all my investigation of the computational universe, I came up with the very general principle that I call the Principle of Computational Equivalence.

What it says is essentially this: that when one sees behavior that isn’t obviously simple, it’ll essentially always correspond to a computation that’s in a sense maximally sophisticated.

One might think that computational ability would be a more gradual phenomenon: that as one increased the complexity of the rules for a system, the system would gradually show greater computational ability.

But PCE says that’s not how it works. It says that above a very low threshold, all systems will be exactly equivalent in their computational capabilities.

And if that’s true, it has some pretty fundamental consequences. About the limits of exact science. About the occurrence of intelligence in the universe. About the phenomenon of free will. About why mathematics is difficult. About new directions in technology.

But is PCE true?

I’m sure it is. But—like many fundamental principles in science—it’s not the kind of thing one can abstractly prove.

Instead, one has to figure out whether it’s true by accumulating evidence—in effect, by doing experiments, and seeing how they come out.

Well, one of the predictions of PCE is that as soon as one sees something like a Turing machine whose behavior is complex, the system will end up being universal—even if its underlying rules are really simple.

And that’s a prediction one can in principle test.

The first big test was in the NKS book: that among the very simplest cellular automata, rule 110 is already universal.

But what about Turing machines? Well, that’s what the prize was about.

And as of today we know that the prediction of PCE also checks out there.

We did an experiment; and PCE was validated.

But unlike some science experiments, it didn’t take a multibillion-dollar particle accelerator. It just took a 20-year-old undergraduate with a PC.

I really wondered what kind of person would win our prize. I gave it about even odds of being a “professional” or an “amateur”.

I didn’t know if the proof would require fancy number theory or other mathematics, accessible only to a “professional”. Or if it could be done purely in explicit “elementary” computational terms.

But at 20:53:59 GMT on Saturday, June 30—just 47 days after we announced the prize—we received a submission, with the description of the submitter given as “Alex Smith is an undergraduate studying Electronic and Computer Engineering at the University of Birmingham, UK. He has a background in mathematics and esoteric programming languages.”

We looked at it. Forty pages of detailed arguments and code. It was clear that it was a serious submission. We started to analyze it.

It had clearly gotten a long way. But it hadn’t quite proved universality—because it still in effect required a separate universal computer to set up each program for the 2,3 machine.

On August 1 we sent back detailed comments. And six days later a revised proof arrived—that got much closer.

We sent copies to our prize committee. One of the members of the committee asked whether the proof really satisfied the formal definition of universality that he’d given in a seminal paper in 1956.

And a few weeks later we received another version clarifying that point.

There’s quite a bit of subtlety. Early definitions of universality assumed that programs for a Turing machine must involve only a finite number of “nonzero bits”—and that the Turing machine must “halt”.

But the 2,3 Turing machine—like modern computers (or systems in nature)—doesn’t “halt”. And in Alex Smith’s construction the Turing machine “tape” (i.e., memory) must be filled with an infinite pattern of bits.

But the key point is that the pattern of bits can be set up without doing universal computation. So that means that when we see universal computation, it’s really being done by the 2,3 machine, not somehow by the encoding we’re using.

What Alex Smith needed to do to establish universality and win the prize was just to show that there’s some way of programming the 2,3 machine to do any computation. That it’s possible to make a “compiler” that compiles “code” for some known class of universal machines to code for the 2,3 machine.

He did that. But his “compiler” doesn’t make terribly compact or efficient code. In fact, for anything but the simplest cases, the code tends to be astronomically large and horrendously inefficient.

But that isn’t the point here. The point is one of principle: the 2,3 Turing machine is universal.

No doubt it’ll be possible to find much better compilers, that make much better code.

And that’ll be interesting. Perhaps one day there’ll even be practical molecular computers built from this very 2,3 Turing machine.

With tapes a bit like RNA strands, and heads moving up and down like ribosomes.

When we think of nanoscale computers, we usually imagine carefully engineering them to mimic the architecture of the computers we know today.

But one of the lessons of NKS—brought home again by Alex Smith’s proof—is that there’s a completely different way to operate.

We don’t have to carefully build things up with engineering. We can just go out and search in the computational universe, and find things like universal computers—that are simple enough that we can imagine making them out of molecules.

I telephoned Alex Smith a few days ago, to tell him that we were finally convinced that he’d solved the problem and earned the prize.

I asked him why he’d worked on it. He said he’d seen it as a nice puzzle. That at first he was pretty sure the Turing machine’s behavior was simple enough that he could prove that it wasn’t universal. But then, as he studied it, he realized that there were little bits of behavior that were more complicated. And it was with these that he managed to show universality.

It’s a thoroughly nice piece of NKS work. Establishing a wonderful monument in the computational universe—a marker at the edge of universality for Turing machines.

We plan an official prize ceremony in a few weeks—fittingly enough, at Bletchley Park, where Alan Turing did his wartime work.

But for now I’m just thrilled to see such a nice piece of science come out.

It’s a very satisfying way to spend $25,000.