(This post was originally posted on the NKS Forum.)

The following are some remarks that I made on the Foundations of Math (FOM) mailing list in connection with discussion of the Wolfram 2,3 Turing Machine Prize. Though much of what I say is well understood in the NKS community, I thought it might nevertheless be of interest here.

Several people forwarded me the thread on this mailing list about our 2,3 Turing machine prize.

I’m glad to see that it has stimulated discussion. Perhaps I can make a few general remarks.

What do we learn from simple universal Turing machines?

John McCarthy wrote:

In the 1950s I thought that the smallest possible (symbol-state product) universal Turing machine would tell something about the nature of computation. Unfortunately, it didn’t.

I suspect that what was imagined at that time was that by finding the smallest universal machines one would discover some “spark of computation”—some critical ingredient in the rules necessary to make universal computation possible. (At the time, it probably also still seemed that there might be a “spark of life” or a “spark of intelligence” that could be found in systems.)

I remember that when I first heard about universality in the Game of Life in the early 1970s, I didn’t think it particularly significant; it seemed like just a clever hack.

But a few decades later—after building up the whole framework in A New Kind of Science, I have a quite different view. Continue reading

(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.

Continue reading