True or false: An intersection of a Turing-recognizable and a regular language is always Turing-decidable.
This was asked on a practice test and the answer is False. Why? I thought regular languages were a subset of decidable languages. So if you intersect regular and recognizable the result would also have to be a subset of decidable.
Is that not correct?
I thought regular languages were a subset of decidable languages. So if you intersect regular and recognizable the result would also have to be a subset of decidable.
There are two confusions here.
First, your seamless switch from "decidable languages" to "recognizable" makes it sound as if you think that decidable and recognizable are the same thing: they're not.
Second, you're confusing the concept of the set of regular languages being a subset of the set of decidable languages with the concept of a particular regular language being a subset of a particular decidable language. Saying that the regular languages are a subset of the decidable languages (which is true) is just saying that every regular language is decidable: this is true. However, that doesn't tell you that every regular language is a subset of every decidable language: it tells you that every regular language is a decidable language. For example, consider $L_1 = \{a^n\mid n\geq 0\}$ and $L_2 = \{a^n\mid n\text{ is prime}\}$. $L_1$ is regular and $L_2$ is decidable but $L_1\not\subseteq L_2$. But the fact that $L_1$ is regular does tell you that $L_1$ is also decidable.
Putting these two things together gives us the following.
If you intersect the set of regular languages with the set of recognizable languages, you get the set of languages $$\{L\mid L \text{ is regular and }L\text{ is recognizable}\}\,.$$ Since every regular language is recognizable, this is just the set of regular languages.
If you intersect an individual regular language $L_1$ with an individual recognizable language $L_2$, you get the set of words $$\{w\mid w\in L_1\text{ and }w\in L_2\}\,.$$ You can prove that this is recognizable (write a recognizer for it!) but it's not necessarily decidable or regular.
A recognizable language is not necessarily decidable. If you intersect such a language with $\Sigma^*$ it doesn't suddenly become decidable.
The intersection is a subset of a decidable set, but so is every language. After all, the language of all strings over a given alphabet is trivially decidable (the decider always says "yes"), and any language is a subset of the language of all strings over its alphabet.
