Decidable and Turing-recognizable languages closed under subtraction Pretty much everything is in the title. I couldn't find the answer anywhere, for some reason.
If I have $L_1$ and $L_2$, which are both decidable, does this necessarily make $L_1 - L_2$ decidable?
What if $L_1$ and $L_2$ are Turing recognizable, is $L_1 - L_2$ Turing recognizable?
Also, if they are not, I would like to understand why.
 A: If both $L_1$ and $L_2$ are decidable, then you can simply run the Turing machines that decide the two languages in sequence in either order.  Both are guaranteed to terminate.  If the TM for $L_1$ accepts a word and the one for $L_2$ rejects it, then the word is in $L_1 - L_2$.  In all other cases, it isn't.
This simple strategy does not work when $L_1$ and $L_2$ are only Turing recognizable, because the TM for $L_2$ may loop on a word not in $L_2$.  (If this word is in $L_1$, it should be accepted, which means that our contraption should halt.)
The fact that a strategy fails does not imply that there is no strategy.  Suppose, however, that the difference of recognizable languages $L_1$ and $L_2$ were recognizable.  Since $\Sigma^*$ (the set of all finite words on alphabet $\Sigma$) is certainly recognizable, the complement of $L_2$ would be recognizable too.  But then $L_2$ would be both Turing recognizable and co-Turing recognizable.  Hence it would be decidable, which cannot be true in general because there exist languages that are recognizable, but not decidable.
In conclusion a general strategy to recognize the difference of recognizable $L_1$ and $L_2$ does not exist.
