3
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ For you extra question: you are right, this is possible, even with many-one reductions: this is because there are undecidable problem which are strictly harder than semi-decidable problems. For instance you can take $L$ to be the set of all (encodings of) deterministic Turing machines that halt on every input. $\endgroup$
    – Rémi
    Dec 31, 2023 at 11:20

1 Answer 1

5
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ thnx for the answer. I will specify it that this is a many-one reduction. In our lecture this is not even mentioned, but after seeing some examples i´m sure my case was about many-one reduction (german Uni system here) $\endgroup$ Jan 1 at 7:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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