# prove decidability and recognizability

I want to prove that for any language $L_1$ described by a Turing machine and any regular language $L_2$, $L_1 \cap L_2$ is described by a Turing machine that its recognizability and decidability is same as $L_1$.

I thought so far that I can describe $L_2$ with a Turing machine. So I can next find the intersection Turing machine of both.

I do not know what to do about the last part of the problem. Maybe I can say that $L_2$ is decidable (because it is regular) and $L_1 \cap L_2$ is a subset of that. So it is also decidable.

The method you propose in your answer is mostly correct. $L_2$ is, indeed, decidable because it's regular. But you can't argue that $L_1\cap L_2$ is decidale because it is a subset of the decidable language $L_2$: every language is a subset of the decidable language $\Sigma^*$ but that doesn't mean that every langauge is decidable.
Hint. You chose the tag , which shows you're on the right lines. $L_1$ is either decidable or recognizable; $L_2$ is both. What do you know about the intersection of two decidable/recognizable languages?
• In the problem, I have to prove that the decidability of the intersect is same as $L_2$. It means that if $L_2$ is recognizable but not decidable, then the intersection is also recognizable but not decidable. – binamu Dec 4 '14 at 9:03
• You have to show that it's the same as $L_1$ but I guess that was just a typo in your comment. You can't go as far as "If $L_1$ is recognizable but not decidable, $L_1\cap L_2$ is recognizable but not decidable", since $L_2$ might be the empty set, which is regular and which gives $L_1\cap L_2=\emptyset$, which is both recognizable and decidable. So the best you can do is that $L_1$ recognizable implies $L_1\cap L_2$ recognizable, and $L_1$ decidable implies $L_1\cap L_2$ decidable. – David Richerby Dec 4 '14 at 9:13