# Why aren't recognizable languages and co-recognizable languages not reducible to each other?

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$$}

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

## 1 Answer

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.