1
$\begingroup$

I know that the decidable are close under: complementation, union, intersection and concatenation?

What about the undecidable languages? I think they are close under complementation, but not under concatenation, union and intersection. But I don't know how to prove it...

My prove

"Lets say L is undecidable lang. Because L is undecidable lang we know one of the following:

  1. there is a word w1 from L that there is no TM that stop for this word

  2. there is a word w2 in L that stopping in reject state in every TM

  3. there is a word w3 Not from L that stopping in accept state in every TM

L' is the complementation lang of L

If 2, the word w2 that stopping in reject state, will stop in the accept state for every TM, but w2 not in L' so L' is Undecidable.

If 3, the word w3 that stopping in accept state, will stop in the reject state for every TM, but w2 is in L' so L' is Undecidable.

If 1, so all the TM are not stopping for w1 so L' is Undecidable???? "

$\endgroup$
7
  • $\begingroup$ @YuvalFilmus you can look at my proof for complementation $\endgroup$ – Jordan Nov 6 '15 at 19:50
  • 2
    $\begingroup$ Unfortunately I'm not your grader. Let them check your proof. $\endgroup$ – Yuval Filmus Nov 6 '15 at 19:51
  • 3
    $\begingroup$ @YuvalFilmus Sure, you're not Jordan's grader. But, when you ask somebody what they tried and they tell you exactly that, dismissing them out of hand doesn't look very good... $\endgroup$ – David Richerby Nov 6 '15 at 21:20
  • $\begingroup$ @DavidRicherby You're welcome to function as Jordan's grader. $\endgroup$ – Yuval Filmus Nov 6 '15 at 21:21
  • 1
    $\begingroup$ Jordan, I suspect the question some folks might be wondering is: "Where did you get stuck? What specifically is your question about your solution/attempt at a proof? What step are you unsure of?" We're not here to act as your grader / proof-checker, but if there is a question about a specific step (e.g., is line 3 valid? here's why I'm not sure), that would be more likely to attract good answers. $\endgroup$ – D.W. Nov 7 '15 at 9:53
2
$\begingroup$

Let $K$ be some undecidable language. Define languages $A_0,A_1,B_0,B_1$ as follows: $$ A_0 = \{ 0 w : w \in K \}, A_1 = \{ 1 w : w \in K \}, \\ B_0 = A_0 \cup \{ 1 w : w \in \{0,1\}^* \}, B_1 = A_1 \cup \{ 1 w : w \in \{0,1\}^* \}. $$ See if you can use these languages to show that the collection of undecidable languages is not closed under concatenation, union or intersection.

As for complementation, try to use the fact that if you can decide a language $L$ then you can decide its complement $\overline{L}$ (why?).

$\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.