Big news from Kurzweil and from Stephen Wolfram’s blog:

University of Birmingham Alex Smith has won a $25,000 prize for proving that the simplest possible Turing machine is in fact universal, Stephen Wolfram has announced.

It has only two states and three colors, yet it can do any calculation that the computer with which you’re reading this blog entry can do. In fact, it can do any calculation that could be performed by a megacomputer consisting of your machine networked to every other machine on the planet.

Wolfram expounds:

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.

So what’s the big deal about a two-state, three-color computer? What can you do with it? Well, that’s the point. It’s a universal machine, so technically you can do anything on it. Anything.

Run Microsoft Excel?

Yep.

Guide nanobots around in your circulatory system?

Sure.

Model an uploaded version of me?

Er, I don’t see why not.

Model entire worlds?

Hmmm…

Wow, that’s a lot to be able to do with two states and three colors. But assuming that those latter two applications are possible at all, there’s no reason why they can’t be done with this machine.