[Solved]: Recursive language subtracted from recursively enumerable language

Problem Detail: 

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?

Asked By : shane

Answered By : Jake

The language that accepts 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 accepts 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 accepted by $L_2$ (which always terminate). We now have a turing machine that outputs all elements of $L_1 - L_2$.

So $L_1 - L_2$ is always recursively enumerable.

Best Answer from StackOverflow

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

3.2K people like this

 Download Related Notes/Documents