I am searching for an undecidable language $L$, such that $L \leq \Sigma^* \setminus L$ and $\Sigma^* \setminus L \leq L$, but I am not able to find a concrete language and reduction. Is there anything like this?

  • $\begingroup$ Why don't you ask your teacher? $\endgroup$ – Gamow Nov 24 '18 at 14:47

Let $K$ be some undecidable problem, and define $$ L = \{0x : x \in K \} \cup \{1y : y \notin K \}. $$ (I'm assuming the alphabet is $\{0,1\}$.) Then $$ \overline{L} = \{\epsilon\} \cup \{0x : x \notin K \} \cup \{1y : y \in K \}. $$ I'll let you take it from here.

| cite | improve this answer | |
  • 1
    $\begingroup$ That's what I was going to answer, too. $\endgroup$ – David Richerby Nov 24 '18 at 23:11

Your Answer

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