[FOM] Simplest universal Turing machine
Vaughan Pratt
pratt at cs.stanford.edu
Thu Oct 25 14:57:24 EDT 2007
Timothy Y. Chow wrote:
> I was wondering if FOM readers have any comment about Stephen
> Wolfram's announcement today:
With the caveat that I haven't looked at the proof myself, I sure do---I
was blown away by it. I had not expected to see this gap completely
closed in my lifetime!
Assuming it is indeed a universal machine, which I take it the committee
is confident of, Alex Smith certainly deserves the credit for completing
the argument, which of itself would appear to have been a tour de force.
But Wolfram himself made key contributions, firstly in having the
confidence even to look at the 2,3 universal machines as a possible
source of universality, second for examining the almost three million
candidates to determine the most plausible candidate, and third for
picking the right candidate as it turned out. Very remarkable.
At the risk of seeming disrespectful it will be interesting to hear the
judgments of the wider community outside the present committee as to
whether all aspects of both the machine itself and the proof hold up
under prolonged inspection, bearing in mind that Kempe's "proof" of the
four-colour theorem held up for a decade.
Vaughan Pratt
More information about the FOM
mailing list