[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