3
$\begingroup$

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 the unsolvability of the halting problem, but the converse might not hold?

1 Answers 1

10

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.

  • 1
    The class of primitive recursive functions has no universal function but all the functions are total.2012-02-16