[FOM] Is Wolfram and Cook's (2, 5) Turing machine really universal?

Vaughan Pratt pratt at cs.stanford.edu
Thu Oct 4 03:13:27 EDT 2012

On 10/2/2012 7:30 PM, Timothy Y. Chow wrote:
> Short of a machine-verifiable formal proof, what constitutes a "fully
> detailed proof" is in the eye of the beholder.

As machines increase in intelligence, what constitutes a 
"machine-verifiable formal proof" is surely in the eye of the machine.

Hughes asked for a "rigorous proof of weak universality."  He defined 
this as "something a young undergraduate could work through centuries 
from now, long after we're all dead and gone, and be 100% convinced of 
the result."  And he pointed out that "Neary and Woods are refreshingly 
honest about the lack of a rigorous proof in their 2009 paper."

There's a big difference between a proof that is not rigorous because it 
does not conform to some system of axioms and one that contains lacunae 
that can't be filled straightforwardly.  The shortcomings of the extant 
proofs would appear to be in the latter category and not at all in the 
former, which no one is asking for.

Vaughan Pratt

More information about the FOM mailing list