# Prove or disprove if $L_{1}$ is Turing-recognizable and $L_{2}$ is co-Turing-recognizable then $L_{1}\cap L_{2}$ is decidable

I thought about these languages: $$L_{1} = A_{TM} = \big\{ \langle M, w \rangle \mid M \text{ is TM and }M \text{ accepts } w \big\}$$ $$L_{2} = \overline{HALT_{TM}} = \big\{ \langle M, w \rangle \mid M \text{ is TM and }M \text{ doesn't halt on input } w \big\}$$

Their intersection: $$L_{1}\cap L_{2} = \big\{ \langle M, w \rangle \mid M \text{ is TM and }M \text{ accepts and doesn't halt on input } w \big\}$$

If I assume that the intersection is decidable by TM $T$ so I can use $T$ to decide $A_{TM}$ and that's a contradiction.

Is it true?

## 1 Answer

Your proof is wrong. Note if $M$ accepts $w$, it must halt on $w$, so $L_1\cap L_2$ is the empty set, which is of course decidable.

To disprove the statement, you can set $L_2$ to be $\Sigma^*$, i.e. the language containing all strings. Since $\emptyset$ is Turing recognizable, $L_2$ is co-Turing recognizable. However, $L_1\cap L_2=L_1$ is undecidable.

• Nitpick: we need to explicitly set $L_1$ so to be undecidable but recognizable, e.g. the halting problem. Otherwise, only knowing that $L_1$ is recognizable does not necessarily imply that it is undecidable. – chi Jul 27 '18 at 10:12
• @chi, right, I just described the change to the proof in OP. – xskxzr Jul 27 '18 at 10:13
• I don't understand your disproving. Did you use these languages: $$E_{TM} = \big\{ \langle M \rangle \mid M \text{ is TM and }L(M)= \emptyset \big\}$$ $$ALL_{TM} = \big\{ \langle M \rangle \mid M \text{ is TM and }L(M)= \Sigma^{*} \big\}$$ What is $L_{1}$ and what is $L_{2}$? – Asaf Jul 27 '18 at 12:37
• @Asaf $L_1=A_{TM}$, $L_2=\Sigma^*=\{s\mid s\text{ can be any string }\}$. – xskxzr Jul 27 '18 at 12:55
• Why $L_{2}$ is co-Turing recognizable? I can use automata that accepts all strings. – Asaf Jul 27 '18 at 13:26