[Solved]: A and B are Turing recognizable, is A - B Turing recognizable?

Problem Detail: 

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.

Not sure if I'm thinking about this correctly...

Asked By : Sam

Answered By : Qalnut

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.)

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/43411