patternMinor
Can I reduce a non semi decidable and undecidable language to a semi decidable and undecidable langauge? many-one reduction
Viewed 0 times
langaugecansemiundecidablenonlanguagedecidablereduceonereduction
Problem
Let's say a Language L is NON-semi decidable and undecidable. Let's also take the Halting problem H, which is a semi decidable and undecidable language.
Is it possible to reduce L to H in a many-one reduction? I know that both are undecidable languages, and we can reduce an undecidable language to another undecidable language, but L being NON-semi-decidable and H being semi decidable kinda gives me the idea that these languages are not compatible, and a reduction is not possible. (Why? Well, I think, we are reducing a "harder" language to an "easier" one. It should be the other way around).
If a reduction was possible, are we reducing to just show the undecidability part of both languages but ignoring the (non) semi-decidable part?
Extra question: Would the other way around be possible? H reduced to L?
I think yes. Well both undecidable, compatible, this part is clear to me. But now we are reducing a semi-decidable language to a non semi-decidable language,which should be "harder". In theory in the lecture when A<B, what we learned is that on the left side of the reduction (A) is max as "hard" as the right side of the reduction (B).
--Edit--
Specified in the title many-one Reduction. As Nathaniel pointed out, there are 2 types of reduction (which I wasn´t aware of) and what I needed in this question was the many-one Reduction.
Is it possible to reduce L to H in a many-one reduction? I know that both are undecidable languages, and we can reduce an undecidable language to another undecidable language, but L being NON-semi-decidable and H being semi decidable kinda gives me the idea that these languages are not compatible, and a reduction is not possible. (Why? Well, I think, we are reducing a "harder" language to an "easier" one. It should be the other way around).
If a reduction was possible, are we reducing to just show the undecidability part of both languages but ignoring the (non) semi-decidable part?
Extra question: Would the other way around be possible? H reduced to L?
I think yes. Well both undecidable, compatible, this part is clear to me. But now we are reducing a semi-decidable language to a non semi-decidable language,which should be "harder". In theory in the lecture when A<B, what we learned is that on the left side of the reduction (A) is max as "hard" as the right side of the reduction (B).
--Edit--
Specified in the title many-one Reduction. As Nathaniel pointed out, there are 2 types of reduction (which I wasn´t aware of) and what I needed in this question was the many-one Reduction.
Solution
It depends on the reduction.
Using a Turing reduction, it is possible. For example, any problem $A$ is Turing-reducible to its complement $\overline{A}$, by puting a negation on an answer given by an algorithm solving $\overline{A}$. If $\overline{A}$ is semi-decidable but undecidable, then $A$ is not semi-decidable (otherwise it would be decidable). If you consider $\overline{A}$ to be the halting problem, then you have your answer.
Note that it is not always possible that such a reduction exists.
Using a many-one reduction, it is not possible, because if $A\leqslant_m B$ and $A$ is not semi-decidable, then $B$ is not semi-decidable, otherwise, you could, for an instance $x$ of $A$, compute $y = f(x)$ using the reduction, and then $x\in A$ if and only if $y \in B$, and you could use the algorithm that solves $B$ partially to solve $A$ partially.
Using a Turing reduction, it is possible. For example, any problem $A$ is Turing-reducible to its complement $\overline{A}$, by puting a negation on an answer given by an algorithm solving $\overline{A}$. If $\overline{A}$ is semi-decidable but undecidable, then $A$ is not semi-decidable (otherwise it would be decidable). If you consider $\overline{A}$ to be the halting problem, then you have your answer.
Note that it is not always possible that such a reduction exists.
Using a many-one reduction, it is not possible, because if $A\leqslant_m B$ and $A$ is not semi-decidable, then $B$ is not semi-decidable, otherwise, you could, for an instance $x$ of $A$, compute $y = f(x)$ using the reduction, and then $x\in A$ if and only if $y \in B$, and you could use the algorithm that solves $B$ partially to solve $A$ partially.
Context
StackExchange Computer Science Q#164768, answer score: 5
Revisions (0)
No revisions yet.