0
$\begingroup$

Prove/disprove that the class of decidable (resp. partially decidable) languages is closed under symmetric difference. A symmetric difference of sets A and B is the set (A \ B) ∪ (B \ A).

I know that the class of decidable languages is closed under symmetric difference, because it is closed under union, complement and intersection. However, does this also apply to the class of partially decidable languages?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Hint: is your class closed under complementation? $\endgroup$
    – Yuval Filmus
    Nov 14, 2018 at 22:04
  • $\begingroup$ @YuvalFilmus I would say the class of partially decidable language is not closed under complement, due to the halting problem when trying to construct a decider for such a language... $\endgroup$
    – Ponsietta
    Nov 14, 2018 at 22:15
  • 1
    $\begingroup$ Now try to answer your question using this information. $\endgroup$
    – Yuval Filmus
    Nov 14, 2018 at 22:17

1 Answer 1

Reset to default
3
$\begingroup$

Assume partially decidable languages are closed under symmetric difference, and let $A$ be a language that is partially decidable but not decidable. Then, where $U$ is the language that includes everything,

$A \otimes U = (A - U) \cup (U - A) = \overline{A}$.

Then $\overline{A}$ must also be partially decidable, and $A$ is decidable; this is a contradiction. (This builds on an answer above, which suggested investigating complementation.)

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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