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