[FOM] Definition of universal Turing machine

[Vaughan Pratt]

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