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

Question

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

If L1 is recursively enumerable but not recursive, and L2 is recursive, then which of the following is the strongest true statement about the set difference L1?L2?

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?

Explanation / Answer

The language that accepts all input strings is recursive. Just create a turing machine that always outputs true. So take that to be L2. L1?L2 would be the empty no matter what L1 is. The empty language is also recursive. So now we have an example of a recursive language arising from L1?L2.

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 L2. Now L1?L2=L1 which is not recursive.

So L1?L2 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 L1 but only output them if they are not accepted by L2 (which always terminate). We now have a turing machine that outputs all elements of L1?L2.

So L1?L2 is always recursively enumerable.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.