No subject

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.