# Are All Turing-Uncomputable Sets Isomorphic to the Halting Problem? [closed]

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

• Cross-posted on cs.se: cs.stackexchange.com/questions/27728/…. – Yuval Filmus Jun 15 '14 at 9:04
• As well as being cross-posted, this is not a research-level question: it's covered by any textbook on computability theory. – David Richerby Jun 15 '14 at 15:20
• 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. – user13675 Jun 16 '14 at 3:02
• The fact that no one is answering only shows we are not interested in answering, which is generally the case for textbook questions here. – Sasho Nikolov Jun 16 '14 at 4:01