0
$\begingroup$

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.

$L(M) = \{A \cap B\}$

But my friend says that the $A \ cap B$ is a subset of $A$, then it is decidable.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.