1
$\begingroup$

Are the undecidable languages closed under complement? How can the answer be proved?

$\endgroup$
2
  • 5
    $\begingroup$ Prove the contrapositive: the complement of a decidable language is decidable. $\endgroup$ Sep 4, 2017 at 10:10
  • 2
    $\begingroup$ Try to prove a more general fact: For any self-inverse function $f : A \to A$, set $B \subseteq A$ is closed against $P$ if and only if $\overline{B} = A \setminus B$ is closed against $P$. $\endgroup$
    – Raphael
    Sep 4, 2017 at 10:34

1 Answer 1

6
$\begingroup$

Suppose you could decide the complement. Wouldn't you then be able to decide the language itself?

$\endgroup$

Your Answer

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

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