patternMinor
Is every undecidable language reducible to any other undecidable language?
Viewed 0 times
undecidableanyeveryreduciblelanguageother
Problem
For the undecidable languages I have seen so far , I am able to give a reduction from one language to other . Is it the case that every undecidable language is reducible to every other undecidable language?
If not can you prove that there exists 2 undecidable languages A and B such that A is not reducible to B.
Note : I am not talking only about mappping reducibility . I am talking about reducibility in general .
If not can you prove that there exists 2 undecidable languages A and B such that A is not reducible to B.
Note : I am not talking only about mappping reducibility . I am talking about reducibility in general .
Solution
There is no concept of "reducibility in general". You always have to specify the power of the reduction. For example, if you allow mapping reductions but with literally any function (not necessarily a computable function) performing the mapping, then any language is reducible to any non-trivial language (i.e., anything other than $\emptyset$ or $\Sigma^*$).
If you do limit the power of the reduction in any way, then there are always pairs of problems $X$ and $Y$ such that $X\not\leq Y$. For example, take any language $X$ that isn't decidable in whatever model of computation you're using to define your reductions. Under that model of reductions, $X\not\leq \{0\}$.
OK, but you asked about undecidable languages and $\{0\}$ isn't undecidable. So, let $H_0$ be the halting problem for the model of computation you're using for your reductions. Let $H_1$ be the halting problem for Turing machines that have an oracle for $H_0$ (if $H_0$ is decidable, this is just the ordinary Turing machine halting problem), and let $H_2$ be the halting problem for Turing machines that have an oracle for $H_1$. Essentially the same proof that the ordinary Turing machine halting problem is undecidable shows that $H_2\not\leq H_1$, and both of these languages are undecidable.
Actually, I don't think that last paragraph is quite right. In the case that your model of reductions is more powerful than Turing machines, you probably need to use the reduction model instead of Turing machines to define the pair of halting problems. I don't have time to fix this right now but I'll come back to it this evening (UK time).
If you do limit the power of the reduction in any way, then there are always pairs of problems $X$ and $Y$ such that $X\not\leq Y$. For example, take any language $X$ that isn't decidable in whatever model of computation you're using to define your reductions. Under that model of reductions, $X\not\leq \{0\}$.
OK, but you asked about undecidable languages and $\{0\}$ isn't undecidable. So, let $H_0$ be the halting problem for the model of computation you're using for your reductions. Let $H_1$ be the halting problem for Turing machines that have an oracle for $H_0$ (if $H_0$ is decidable, this is just the ordinary Turing machine halting problem), and let $H_2$ be the halting problem for Turing machines that have an oracle for $H_1$. Essentially the same proof that the ordinary Turing machine halting problem is undecidable shows that $H_2\not\leq H_1$, and both of these languages are undecidable.
Actually, I don't think that last paragraph is quite right. In the case that your model of reductions is more powerful than Turing machines, you probably need to use the reduction model instead of Turing machines to define the pair of halting problems. I don't have time to fix this right now but I'll come back to it this evening (UK time).
Context
StackExchange Computer Science Q#63327, answer score: 7
Revisions (0)
No revisions yet.