Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sorry this might be a layman question, but I could not find any information on this.

Is the fact that there exists no Turing machine that can solve the halting problem equivalent to the existence of universal Turing machines? Universality seems to imply unsolvability of the halting problem, but the converse might not hold?

share|improve this question

1 Answer 1

up vote 7 down vote accepted

Well, the two propositions are equivalent in the trivial sense that both are true (and provable) statements about Turing machines.

However, they are not equivalent in the sense that if you have an unknown class of machines and know only that they cannot solve the halting problem (either for the class itself or for Turing machines) then you can conclude that there's an universal machine among them.

For example, consider a class of machines that contain only two machines: One that ignores the input and immediately outputs 1; and one that ignores the input and loops forever. Certainly neither of them can solve any halting problem, but still neither of them is universal.

share|improve this answer
    
I am not sure if I get your answer. I try to reformulate the question more precisely. Assume you have an unknown class of countably infinite many machines. Then you say that if you know that they cannot solve the halting problem, there is an universal machine among them, but the converse (if you know that there is an UM among them, then they cannot solve the halting problem) does not hold? –  corto Feb 14 '12 at 10:20
    
No, on the contrary: I deny that if you know they cannot solve the halting problem then there must be a universal machine among them. This holds even if there are infintely many machines in the class; for example all machines that always produce constant output without reading their input, plus a machine that always diverges. –  Henning Makholm Feb 14 '12 at 16:07
    
Ah ok I see. But in your first answer you wrote: "if you have an unknown class of machines and know only that they cannot solve the halting problem [...] then you CAN conclude that there's an universal machine among them." So I guess you meant "cannot" not "can"? And what about the other direction? (If you have an unknown class of countably infinite many machines and you know that there is a universal machine among them, can you conclude that they cannot solve the halting problem?) –  corto Feb 15 '12 at 9:54
    
@corto: I wrote: "they are not equivalent in the sense that if you have .. and know ... then you can conclude ...". (Emphasis added). As for the other direction: a class of machine that contains a universal machine for the class itself cannot solve the halting problem for the class itself -- as the standard diagonalization argument proves. On the other hand, for example, the class of all oracle machines contains both a universal Turing machine simulator, and a halting oracle for ordinary Turing machines. –  Henning Makholm Feb 15 '12 at 15:26
1  
The class of primitive recursive functions has no universal function but all the functions are total. –  Carl Mummert Feb 16 '12 at 1:00

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.