HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Does Halts reduce to all other undecidable languages?

Submitted by: @import:stackexchange-cs··
0
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?

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.

Context

StackExchange Computer Science Q#99713, answer score: 2

Revisions (0)

No revisions yet.