It is perhaps ironic that two weeks after releasing what is probably the single most complex computational system ever constructed, we are today announcing a prize for the very simplest of computational systems.

But today is the fifth anniversary of the publication of A New Kind of Science, and to commemorate this, we have decided to establish the first NKS prize.

The prize is related to a core objective of the basic science of NKS: to map out the abstract universe of possible computational systems.

We know from NKS that very simple programs can show immensely complex behavior. And in the NKS book I formulated the Principle of Computational Equivalence that gives an explanation for this discovery.

That principle has many predictions. And one of them is that the ability to do general-purpose computing—to be capable of universal computation—should be common even among systems with very simple rules.

Today’s CPUs have millions of components. But the Principle of Computational Equivalence implies that all kinds of vastly simpler systems should also support universal computation.

The NKS book already gives several dramatic examples. But the purpose of the prize is to determine the boundary of universal computation for a particularly classic type of computational system: Turing machines.

Invented by Alan Turing in 1936 as the first successful abstract models of computation, Turing machines have been widely used in theoretical computer science.

But until the whole framework of NKS, looking at specific simple Turing machines seemed merely to be a curiosity. And indeed, even though he certainly had the capabilities to do it, I do not believe that Alan Turing ever himself actually explicitly simulated any Turing machine at all.

In the NKS book, I found what is currently the simplest known universal Turing machine—with 2 states and 5 colors.

I also did an extensive search of simpler Turing machines. And in doing that I found a much simpler candidate for universality: the following 2,3 Turing machine:

I did quite a bit of analysis on this machine. But I wasn’t able to show either that it was universal, or that it wasn’t.

It’s really easy to simulate this in Mathematica. In fact, in Mathematica 6 we just added a built-in Turing machine function. So running this machine for t steps is just:

TuringMachine[{596440, 2, 3}, {1, {{}, 0}}, t]

Over the last five years, we have done a variety of kinds of things to help support the growing NKS community.

Today we are adding one more: we are establishing our first NKS prize.

We’re offering $25,000 to the first person or group who can determine whether the 2,3 Turing machine above is actually universal, or not—and can provide the proof.

All the details are at www.wolframprize.org.