10
$\begingroup$

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.

Improve this question
$\endgroup$
1

3 Answers 3

Reset to default
7
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ Indeed and thanks David. I got confused thinking about this and flipped a bit in the problem statement. Edited. $\endgroup$
    – Tim
    Commented Jun 15, 2014 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
    Commented Jun 15, 2014 at 20:16
4
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\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
    Commented Mar 14, 2015 at 21:04
  • $\begingroup$ Clarification: I'm assuming by "reduces to it", you mean via a Turing reduction. $\endgroup$
    – Marcel Besixdouze
    Commented Mar 14, 2015 at 21:12
  • $\begingroup$ I mean many-one reduction. $\endgroup$
    – user16480
    Commented Mar 15, 2015 at 22:10
2
$\begingroup$

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.

Improve this answer
$\endgroup$

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