<p>No, there is a whole hierarchy of Turing undecidability:
<a href="http://en.wikipedia.org/wiki/Turing_degree" rel="nofollow noreferrer">http://en.wikipedia.org/wiki/Turing_degree</a></p>
<p>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).</p>

CC BY-SA 4.0
2014-06-15T07:26:06.540Z
2021-07-13T10:48:06.247Z
2021-07-13T10:48:06.247Z
Aryeh
<p>We know from computability theory that some sets are recursively computable on a Turing machine and others not.</p>

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

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

<p>Furthermore, the proof that the Kolmorov complexity is uncomputable classically uses the Halting problem.</p>

<p>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?</p>

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

CC BY-SA 3.0
2014-06-15T09:04:55.200Z
Cross-posted on cs.se: http://cs.stackexchange.com/questions/27728/are-all-undecidable-uncomputable-problems-reducible-to-the-halting-problem.
Yuval Filmus
CC BY-SA 3.0
2014-06-15T15:20:39.073Z
As well as being cross-posted, this is not a research-level question: it's covered by any textbook on computability theory.
David Richerby
CC BY-SA 3.0
2014-06-16T03:02:44.517Z
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
CC BY-SA 3.0
2014-06-16T04:01:28.913Z
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
<halting-problem>
Are All Turing-Uncomputable Sets Isomorphic to the Halting Problem?
user13675
# Are All Turing-Uncomputable Sets Isomorphic to the Halting Problem?

(Asked by: username_0 on 2014-06-15)

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

**Tags:** halting-problem

> **Comments:**
> **username_1**: Cross-posted on cs.se: http://cs.stackexchange.com/questions/27728/are-all-undecidable-uncomputable-problems-reducible-to-the-halting-problem.  
> **username_2**: As well as being cross-posted, this is not a research-level question: it's covered by any textbook on computability theory.  
> **username_0**: 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.  
> **username_3**: The fact that no one is answering only shows we are not interested in answering, which is generally the case for textbook questions here.  

---

## 1 answers

### Answer by username_4 on 2014-06-15. Score: 3

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


---

