1
$\begingroup$

While learning to prove undecidability of problems, I came across a statement that you can't reduce a recognizable language to a co-recognizable language and vice-versa to prove undecidability. Why is it so?

Eg: Halting problem of TMs can't be reduced to Emptiness problem of TM

$\qquad$ $H_{TM}$ = {$\langle M,x \rangle$|$M$ is a TM and $M$ halts on input $x$}

$\qquad$ $E_{TM}$ = {$\langle M \rangle$|$M$ is a TM and $L(M)= \emptyset$}

$\endgroup$
  • $\begingroup$ If you can reduce a recognizable language to a co-recognizable problem, then the former is in fact decidable. $\endgroup$ – Yuval Filmus Nov 11 '18 at 0:50
1
$\begingroup$

Suppose that $L_1$ is recognizable, $L_2$ is co-recognizable, and there is a computable reduction from $L_1$ from $L_2$. The computable reduction shows that $L_1$ is also co-recognizable, and so decidable.

We conclude that if $L_1$ is recognizable but not decidable, then it cannot be reduced to any co-recognizable language.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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