patternMinor
Does Halts reduce to all other undecidable languages?
Viewed 0 times
haltsundecidablealllanguagesreducedoesother
Problem
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?
Are there any undecidable languages which Halts does not reduce to?
Solution
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.
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.
Context
StackExchange Computer Science Q#99713, answer score: 2
Revisions (0)
No revisions yet.