0
$\begingroup$

For example:

If the XOR operation on two languages, A and B, is described as: $A\;\mathrm{XOR}\;B = (A \cup B) \setminus (A \cap B)$,

1) How can we prove that the set of enumerable languages is closed under the XOR operation?

2) How can we prove that the set of decidable languages is closed under the XOR operation?

$\endgroup$
  • 1
    $\begingroup$ What do you mean by "an enumerable/decidable group of languages"? Enumerability/decidability is usually a property of langauges, not sets of languages. One could talk about an enumerable/decidable set of languages but Rice's theorem usually means that the concept isn't very interesting at all. $\endgroup$ – David Richerby Dec 24 '15 at 11:37
  • 3
    $\begingroup$ Assuming that you mean "a set of enumerable/decidable languages", what did you try? Where did you get stuck? We're happy to help with conceptual questions but just solving homework-style exercises for you is unlikely to help you understand better. $\endgroup$ – David Richerby Dec 24 '15 at 11:37
  • $\begingroup$ Thanks for responding so soon and for correcting me. I did mean "languages" instead of "group of languages". Unfortunately, I don't even know how to begin. I know that I need to assume that A and B are enumerable languages (in the first question), and then I need to find a TM that will accept those languages. am I correct? If so, I truly don't know how to continue. I'm not asking for you to solve this specific question, but could you please explain the steps that I need to perform in order to solve questions of this kind in general? thank in advance $\endgroup$ – eevee25 Dec 24 '15 at 12:01
  • 3
    $\begingroup$ Yes, you need to show either that (a) given any two enumerable language, there's a Turing machine that accepts their XOR or (b) there are two enumerable languages whose XOR is not enumerable; and similarly for the second part. The second part is somewhat easier, by the way, so I suggest you try that first. $\endgroup$ – David Richerby Dec 24 '15 at 12:07
2
$\begingroup$

Here is a similar example, with the minority operator: the minority of three languages $A,B,C$ consists of words belonging to at most 1 of $A,B,C$.

If $A,B,C$ are decidable then so is their minority. Indeed, given a word $w$, first determine whether $w$ belongs to $A$, to $B$, and to $C$. You can do this since $A,B,C$ are decidable. Depending on this data, either accept or reject $w$. This is an algorithm deciding the minority.

If $A,B,C$ are enumerable, then their minority need not be so. Indeed, let $A$ be a language which is enumerable but not co-enumerable (for example, the set of halting programs). The minority of $A,A,A$ consists of all words not in $A$, i.e., the complement of $A$. By assumption $A$ is not co-enumerable, so the minority of $A,A,A$ is not enumerable.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.