Theory of computation tells us that there are some languages that cannot be recognized by a Turing machine. That is, there are well-defined problems for which no Turing machines can provide an algorithm which solves the problem.

Many problems that are undecidable seem to have a reduction to the Halting problem: Matyasevich's proof of the undecidability of Diophantine equations uses the Halting problem, the machine equivalence problem uses the Halting problem as well...

The question is: are all undecidable problems (in the sense of Turing) reducible to the Halting problem?

If so, is there a proof of this? If not, is there a counterexample of such a problem that provably cannot be reduced or mapped to the Halting problem.


No. As I recall a practical example can be made out of a function inequivalence statement. More abstractly, there is something called Turing-degree in undecidability and infinite levels of "hardness". Each level has it's own Halting Problem strictly harder than those at every level lower. Check out the first section of this Scott Aaronson lecture and what he calls a "Super Halting Problem".

  • $\begingroup$ Indeed and thanks David. I got confused thinking about this and flipped a bit in the problem statement. Edited. $\endgroup$ – Tim Jun 15 '14 at 8:54
  • $\begingroup$ In addition, the Halting problem is recursively enumerable. Even without a Turing degree argument, it is easy to come up with problems that don't reduce to the halting problem. $\endgroup$ – user16480 Jun 15 '14 at 20:16

The halting problem is recursively enumerable, but not co-recursively enumerable. That is, it is recognizable, but it's compliment is not. You are sure to halt on a string in the language, but not on a string that is not in the language.

Implication of not $r.e.$ and not $co\text{-}r.e$ propagate from left to right over a reduction. Implication of $r.e.$ and $co\text{-}r.e$ propagate from right to left over a reduction.

Because the halting problem is $r.e.$, any problem that reduces to it is $r.e.$ So if all undecidable languages reduced to the halting problem, then all undecidable languages would be $r.e.$, but some undecidable languages are neither $r.e.$ nor $\text{co-r.e.}$, and some are $co\text{-}r.e$ but not $r.e.$

An example of an undecidable language that doesn't reduce to $\text{HALT}$ is $\text{EMPTY} = \{ <M> : \text{M is a Turing machine and } L(M) = \emptyset\}$

$\text{EMPTY}$ is a language which is $co\text{-}r.e$, but not $r.e.$. This is because as soon as you find a string that $M$ accepts, you know that L(M) is not empty, and if a string is in $L(M)$ it is guaranteed to be accepted and therefore halt, in a finite amount of time. But if $M$ doesn't accept any strings, you may never know that as the machine may diverge or go into an infinite loop on a string and never halt.

Another language that doesn't reduce to $\text{HALT}$ is $ FINITE = \{<M> : M \text{ is a Turing machine and L(M) is finite } \}$, which is neither $r.e.$ nor $\text{co-r.e.}$

  • $\begingroup$ "Because the halting problem is r.e., any problem that reduces to it is r.e.". This is obviously false. The complement of the halting problem is reducible to the halting problem, but it is not r.e.. It is, however, limit computable (the limit computable sets are exactly those reducible to an r.e. set, i.e. those sets reducible to the halting problem). $\endgroup$ – Marcel Besixdouze Mar 14 '15 at 21:04
  • $\begingroup$ Clarification: I'm assuming by "reduces to it", you mean via a Turing reduction. $\endgroup$ – Marcel Besixdouze Mar 14 '15 at 21:12
  • $\begingroup$ I mean many-one reduction. $\endgroup$ – user16480 Mar 15 '15 at 22:10

The proof that the halting problem is undecidable relativizes, that is, it still works if the Turing machine is given access to an oracle. In particular, the halting problem for Turing machines with oracle access to the (usual) halting problem isn't solvable by Turing machines with oracle access to the (usual) halting problem. This implies that this generalized halting problem cannot be many-one reduced to the (usual) halting problem.

More generally, we can construct a scale of problems, each one harder than the previous one, by adding the appropriate oracle. This is the classical "jump" operator of recursion theory. If you're interested in this sort of thing, find a textbook or lecture notes on recursion theory.


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