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