Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
I am discussing with a friend the following question:
If the language $A$ is decidable and the language $B$ is recognizable, Then the language $A \cap B$ is recognizable?
I believe it is. My point is that if the machine that recognizes B never halt in some string, so the bigger machine will never know what to answer.
The image makes my point.
But my friend says that the $A \ cap B$ is a subset of $A$, then it is decidable.
You are correct, without further information we can only say that $A\cap B$ is recognizable.
A simple example would be to let $B$ be any recognizable (but not decidable) language - the Halting Problem for example, if you want to be melodramatic, and let $A = \Sigma^{\ast}$. Then $A \cap B = B$, so clearly can't be decidable.
It is of course possible that the intersection happens to be decidable, (for example if $A \cap B = \emptyset$ is a trivial example), but this may not be true in general.
