# A and B are Turing recognizable, is A - B Turing recognizable?

If A and B are Turing recognizable, is A - B Turing recognizable?

I think that A - B would be Turing recognizable because they're both in the space of Turing recognizability. For example, if A is context free and B is a regular language A - B would result in a language that is sill Turing recognizable.

However, does this become a question about emptiness? Two Turing recognizable languages equal to each other leave an empty set. Is the empty set Turing recognizable? I would still say yes.

• Hint: what is another way of writing $A-B$? – Ryan Jun 8 '15 at 22:35
• ... or when $A=\Sigma^*$? – Ran G. Jun 8 '15 at 22:37
• Also, consider the asymmetry of the definition of Turing recognizability (i.e., that a recognizer says "yes" in a rather different way to how it says "no"). – David Richerby Jun 8 '15 at 22:57
• Please, Alan Turing is a great scientist, and even if he were not, he would still be entitled to a name starting with a capital letter. He deserves it considerabl;y more than Mr Context Free. – babou Jun 8 '15 at 22:57
• Unfortunately, no. $A\setminus B$ is indeed a subset of $A$, a recognizable language, but generally a subset of a language with a certain property will not have that property. For an extremely simple example, let $B$ be a finite language and $A=\Sigma^*$. Then $A\setminus B$ is certainly not finite. – Rick Decker Jun 9 '15 at 0:00

Suppose that $L$ is a Turing-recognizable language and $L^C$ is its complement. Let's assume, for the purposes proof by contradiction, that $L^C$ is also Turing-recognizable. This means that a recognizer exists for each of these two languages: we will call them $M_L$ and $M_{L^C}$. How might we use these two recognizers to do something absurd?

For starters, we can construct a decider for the language $L$. Given any string $w$, we can use it as input for both $M_L$ and $M_{L^C}$. $M_L$ will halt and accept if $w$ is in $L$ (and halt and reject or loop forever if not). Conversely, $M_{L^C}$ will halt and accept if $w$ is in $L^C$ (and halt and reject or loop forever otherwise). In any case, our constructed machine will halt with a decision about $w$, and so we've proven the existence of a decider for $L$.

By assuming that any Turing-recognizable language $L$ is closed under complement, we can show that $L$ is also Turing-decidable, which implies that $R=RE$. So we must conclude that Turing-recognizable languages are not closed under complement!

If they're not closed under complement, is it possible for them to be closed under set difference? (Hint: the set of Turing-recognizable languages is closed under intersection. Can you rewrite $A-B$ in terms of complement and intersection?)

(Solution: $A-B$ can be written $A \cap B^C$; loosely speaking, both describe the set of elements which belong to $A$ but not to $B$. Since set difference can be expressed using intersection and complement operators, and since Turing-recognizable languages are not closed under complement, we conclude that Turing-recognizable languages are not closed under set difference.)

• A intersect B is equal to (A complement union B complement) complement – Yawn Jun 9 '15 at 1:06
• Maybe A - B is equal to A intersect B complement – Yawn Jun 9 '15 at 1:11
• That's right. $A - B$ is 'the set of elements which are in $A$ except for those in $B$.' Since $A \cap B$ is 'the set of elements in both $A$ and $B$' and $B^C$ is 'the set of elements which are not in $B$,' then $A \cap B^C$ is 'the set of elements which are in $A$ and not in $B$.' Which is $A - B$! – Qalnut Jun 9 '15 at 1:38