Recursive language subtracted from recursively enumerable language

Question

This is a homework problem but I am awfully confused. The problem reads as follows:

If $L_1$ is recursively enumerable but not recursive, and $L_2$ is recursive, then which of the following is the strongest true statement about the set difference $L_1 - L_2$?

a. It must be recursively enumerable and not recursive.

b. It might be neither recursively enumerable nor recursive.

c. It must be recursively enumerable and it might be recursive.

d. It must be recursive.

I understand exactly what a recursive language and recursively enumerable languages are. A recursive language is one for which there exists a Turing machine which halts and decides whether the string is in the language for all strings of the alphabet. A recursively enumerable language is one for which there exists a Turing machine which halts and accepts if the string is in the language, but may halt and reject or not halt for strings that are not on the language.

So an example of a recursively enumerable language would be all C programs which do not contain an infinite loop (since we obviously won't halt if the program does). I am a tad bit confused on finding an example of a recursive language.

So subtracting a recursive language from a recursively enumerable language means that, if I try to think this through, there exists a turing machine which may halt and accept all strings in the language, and removing a recursive language only means we remove some strings which would be halted on and accepted.

So I am leaning towards c, but I am very fuzzy. Any pointers?

Answer 1

The language that contains all input strings is recursive. Just create a Turing machine that always outputs true. So take that to be $L_2$. $L_1 - L_2$ would be the empty no matter what $L_1$ is. The empty language is also recursive. So now we have an example of a recursive language arising from $L_1 - L_2$.

The language that contains no input strings (the empty language) is recursive. Just create a Turing machine that always outputs false. So take that to be $L_2$. Now $L_1 - L_2 = L_1$ which is not recursive.

So $L_1 - L_2$ may or may not be recursive.

Now we are left with b) and c). To decide between these we can note that the language is always recursively enumerable. Proof:

Iterate outputs from $L_1$ but only output them if they are not contained in $L_2$ (check by a Turing machine which always terminates). We now have a Turing machine that outputs all elements of $L_1 - L_2$.

So $L_1 - L_2$ is always recursively enumerable.

Answer 2

If it is established that $L_2$ is a proper $-$ and non-empty $-$ subset of $L_1$, then $L_1 - L_2$ must be recursively enumerable, but not recursive. If that wasn't the case, you would be able to combine the Turing machines that decide for the presence of a word in $L_1 - L_2$ and $L_2$ to have $L_1$ proved recursive.

However, $L_2$ might not be a proper subset of $L_1$ (assuming you can even decide that!), so $L_1 - L_2$ brings us no additional information, and the strongest thing we can conclude, without knowing any further, is that $L_1 - L_2$ is recursively enumerable.