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?
Intersection of Turing-recognizable language and regular language
turing machines;regular languages;automata
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.