3
$\begingroup$

In a CS theory class I'm taking, we showed Halts was undecidable via a diagonalization argument. All other undecidable problems we looked at we either got by reducing Halts to them, or some chain of reductions that started with Halts. Are there any undecidable languages which Halts does not reduce to?

$\endgroup$
  • $\begingroup$ By "Halts", you mean the ordinary halting problem for Turing machines? (Input is a description of a Turing machine and an input for it, output is "yes" if the machine halts on that input and "no" if it doesn't.) $\endgroup$ – David Richerby Nov 7 '18 at 14:47
  • $\begingroup$ After looking at the answers, I hope another answer might tell, are there any (natural or constructive) undecidable languages which neither $HALT$ nor $\overline{HALT}$ reduce to? I added "natural or constructive" since the languages that can be reduced to are apparently(?) countable. If there are none, does it mean undecidability is inherently related to self-reference? $\endgroup$ – Apass.Jack Nov 18 '18 at 16:53
2
$\begingroup$

Recall that $A \leq_m B$ iff $\bar A \leq_m \bar B$. Indeed, the same reduction function works for both cases.

So, let $H$ be the halting problem. Both $H,\bar H$ are undecidable. We prove $H \not\leq_m \bar H$.

By contradiction, assume $H \leq_m \bar H$. Hence, by the property above, $\bar H \leq_m H$. Hence $\bar H$ reduces to some RE problem, making $\bar H$ RE as well. Since $H,\bar H$ are both RE, we conclude that both are decidable. Contradiction.

$\endgroup$
0
$\begingroup$

$\mathrm{HALT}$ does not reduce to $\overline{HALT}$. Otherwise, all the arithmetical hierarchy would collapse to $\mathrm{R}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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