# Halting problem and universality

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?

-

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.

-
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
The class of primitive recursive functions has no universal function but all the functions are total. –  Carl Mummert Feb 16 '12 at 1:00
show 1 more comment