Simplest Turing Machine Is Universal

By | October 26, 2007
2 Comments

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.

Simplestturing.jpg

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.

  • Karl Hallowell

    A few things here. First, Turing machines aren’t good for practical applications. They run too slowly and the tape required can be huge.

    Second, they are good for theoretical applications because every physical (classical not quantum) computer can be shown to be equivalent to a Turing machine with a finite tape. Then you can use the simplicity of the Turing machine to find provable statements that will apply to all computers.

    Finally, simple computimg machine models might have a role either in building prototypes or embedding computing machines into larger systems. For example, in creating a deterministic life form or as “DNA” in a genetic algorithm. It’s probably easier to quantize a particular simple Turning machine than to quantize an abstract Turing machine. (BTW, the states of the overall system are all possible states of the Turning machine, it’s location on the tape, and all possible states of the tape, the latter is infinite.)

  • Phil Bowermaster

    On the applications I named (as they say in the commercials) — it’s not that you would, but you could.