1
$\begingroup$

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

$\endgroup$
  • 5
    $\begingroup$ Prove the contrapositive: the complement of a decidable language is decidable. $\endgroup$ – Yuval Filmus Sep 4 '17 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 '17 at 10:34
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, privacy policy and cookie policy

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