[FOM] Definition of universal Turing machine

[Martin Davis]

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'.

This is also a reply to Harvey Friedman's query about "my" definition.

But, as I said in an earlier message, although the committee was kept 
informed, we were never polled.

Martin


                           Martin Davis
                    Visiting Scholar UC Berkeley
                      Professor Emeritus, NYU
                          martin at eipye.com
                          (Add 1 and get 0)
                        http://www.eipye.com