We know from computability theory that some sets are recursively computable on a Turing machine and others not.

Many such sets or languages that cannot be recognized by a Turing machine seem to have a reduction to the Halting problem.

Matyasevich's proof of the undecidability of Diophantine Equations (following Robinson, Putnam and Davis) uses the Halting problem. The machine equivalence problem uses the Halting problem and Chaitin's Omega uses the Halting problem as well.

Furthermore, the proof that the Kolmorov complexity is uncomputable classically uses the Halting problem.

This is an intuition, but are all languages that cannot be recognized by a Turing machine isomorphic or reducible to the Halting problem, that is, provably reducible?

It seems that by definition, a language that is recognizable by a Turing machine is such that there exists a Turing machine that halts on all inputs from that language. The inverse is then that the machine does not halt... and therefore all such problems are equivalent, by definition, to the Halting problem...

  • 4
    $\begingroup$ Cross-posted on cs.se: cs.stackexchange.com/questions/27728/…. $\endgroup$ Jun 15 '14 at 9:04
  • 2
    $\begingroup$ As well as being cross-posted, this is not a research-level question: it's covered by any textbook on computability theory. $\endgroup$ Jun 15 '14 at 15:20
  • $\begingroup$ Perhaps, but seems that nobody is actually providing an answer, for a problem that's in "every textbook". Simple question: are all Turing-undecidable problems isomorphic to the Halting problem. Yes. No. Proof. $\endgroup$
    – user13675
    Jun 16 '14 at 3:02
  • 2
    $\begingroup$ The fact that no one is answering only shows we are not interested in answering, which is generally the case for textbook questions here. $\endgroup$ Jun 16 '14 at 4:01

No, there is a whole hierarchy of Turing undecidability: http://en.wikipedia.org/wiki/Turing_degree

In particular, the language L_min consisting of all minimal Turing machine encodings is not reducible to L_halt. (A TM encoding is minimal if there is no shorter encoding of an equivalent TM).


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