prove decidability and recognizability

Question

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.

I am not sure whether my approach is correct or not. Please help me.

• Raphael: Hint: How do you show that the intersection of two regular languages is regular?

Answer 1

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 closure-properties, 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?

• binamu: I know that intersection of two decidable is decidable and intersection of two recognizable is recognizable. What can we say about intersection of a decidable language and a recognizable language (which is not decidable)?
• David Richerby: Any language taht is decidable is also recognizable so it's enough to look at the intersection of two recognizable languages.
• binamu: 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.
• David Richerby: 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.