[FOM] Definition of universal Turing machine
Vaughan Pratt
pratt at cs.stanford.edu
Sat Oct 27 19:27:26 EDT 2007
Martin Davis wrote:
> Vaughan Pratt wrote:
> >On the technical question as to the definition of "universality," it
> >is customary at the "low" end to call a machine universal just when it
> >has an undecidable halting problem,
>
> That's a bad "custom". At the least one would require that the
> halting set be Turing complete, i.e. of Turing degree 0'.
I was shooting only for an informal notion at that point (but in that
case you're right that I shouldn't have said "customary"). My formal
definition hopefully more than addressed your concern by specifying K to
be r.e.-complete.
("More than" in that degree 0', while stronger than nonzero degree, is
still somewhat broad, being closed under complement; the r.e.-complete
sets form a proper subclass of degree 0' that is not so closed. Turing
degree 0' isn't my favorite criterion for a formal definition of
universality, which I would rather define to within many-one
reducibility, finer than Turing reducibility, thereby avoiding
classifying the co-r.e.-complete sets as universal which seems unnatural.)
("Undecidable halting problem" is equivalent to "nonzero Turing degree,"
strictly weaker than Turing degree 0' by the Friedberg-Muchnik theorem,
Muchnik 1956, Friedberg 1957, same years as the two papers of yours you
cited.)
The appropriate approach to weakening to accommodate the two-state
machine seems to me not to fiddle with K but to allow a more generous
halting criterion H than mere recognition that the machine has entered a
halting state. My first attempt at such an H was too generous and I cut
it back to "recursive in |w|" in the follow-up message.
Vaughan
More information about the FOM
mailing list