Problem Detail: I have two sets B which is recursively enumerable and is not recursive, and A which is recursive. Is $A-B$ recursive and / or recursively enumerable? What about $B-A$? $B-A$ is obviously recursively enumerable (to generate its elements, I can generate B’s elements and check if they are in A). If A is the empty set or $A cap B$ is the empty set, it’s easy. Otherwise, I believe $B-A$ is not recursive (I can’t tell if a number is in B, since B is not recursive) and $A-B$ is not recursively enumerable (I can generate A’s elements, but I can’t check if they are in B), so it’s not recursive either. Am I wrong? How can I actually (and formally) prove any of those?
Answered By : babou
The empty set is recursive, hence B cannot be the empty set. You are right the B-A is recursively enumerable. You cannot prove B-A is not recursive for a good reason: it may be recursive. Maybe you can imagine an example of A recursive, B not recursive, and B-A recursive. Hint: it is not even necessary that B be recursively enumerable, or A recursive.
Proof that $B-A$ can have properties more specific than recursively enumerability (i.e. compatible with being recursively enumerable),
indpendently of the properties of B.
Consider 2 disjoint alphabets $Sigma$ and $Sigma’$, such that $SigmacapSigma’=emptyset$. Take $C=Sigma’,^*$ and $A=Sigma^*$. Let $E$ be a non-recursive language in $Sigma^*$. Let $B=Ccup E$. Then $B$ is a non-recursive language on the alphabet $SigmacupSigma’$, because $C$ is recursive (trivially). Now you can see that $B-A=C$ since substracting $A$ removes precisely $E$, i.e. all words in B that are in $Sigma^*$. So you have $B$ non-recursive, and both $A$ and B-A are recursive. Here I chose $A$ recursive. But I could have chosen any non-recursive language on $Sigma^*$ that contains $E$.
Similarly, you cannot prove anything about A-B. Think why.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/33975 3.2K people like this
Download Related Notes/Documents
Related
