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


closed as off-topic by Jeffε, Marzio De Biasi, Hsien-Chih Chang 張顯之, Kaveh, Lev Reyzin Jun 16 '14 at 4:57

This question appears to be off-topic. The users who voted to close gave these specific reasons:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Jeffε, Kaveh, Lev Reyzin
  • "Our site policy prohibits simultaneous crossposting: it duplicates effort and fractures discussion. Crossposting is permitted after a week has passed without a satisfying answer elsewhere. When crossposting please summarize the relevant discussions from other sites in your question and link between the copies in both directions." – Marzio De Biasi, Hsien-Chih Chang 張顯之
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 4
    $\begingroup$ Cross-posted on cs.se: cs.stackexchange.com/questions/27728/…. $\endgroup$ – Yuval Filmus 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$ – David Richerby 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
  • 1
    $\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$ – Sasho Nikolov 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_max 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.