0
$\begingroup$

I've been learning about TMs in class lately and we talked about the decidability of two languages by union or intersection. I was wondering if you have two decidable languages, L1 and L2, is their difference L1 - L2 also decidable?

$\endgroup$
  • $\begingroup$ $L_1-L_2$ is $L_1\cap \overline{L_2}$ $\endgroup$ – rici Feb 25 at 4:37
  • $\begingroup$ I was looking into how to use this relationship earlier but only know that L1 is decidable if and only if both L1 and L1¯¯¯¯¯¯ are recognizable. Also that decidable languages are closed under intersection and complement. I'm just not sure if the same applies to intersection of the complement, and how to extend this to any two different languages unless i'm missing something sorry? $\endgroup$ – Dan Feb 25 at 4:50
  • 1
    $\begingroup$ So $\overline {L_2}$ is decidable, right? (Closed under complement). Then what does closed under intersection tell you? $\endgroup$ – rici Feb 25 at 5:02
  • $\begingroup$ Okay I think (and hope) I get it now! So what I think now is that if L1 and L2 are decidable, both complements are also. So if it's two decidable languages' intersection, then L1 - L2 should also be decidable then? $\endgroup$ – Dan Feb 25 at 5:11
  • $\begingroup$ Yes, I think you got it. $\endgroup$ – rici Feb 25 at 13:21
0
$\begingroup$

We know that if a language $L$ is decidable, then the complement $\overline{L}$ is also decidable, since we can simply reverse the accept and reject conditions in the Turing machine deciding $L$.

Furthermore, if $L_1$ and $L_2$ are decidable languages, then their intersection $L_1 \cap L_2$ is decidable, since we can accept if both the Turing machines for $L_1$ and $L_2$ accept, and reject if one of them rejects.

Since $L_1 - L_2 = L_1 \cap \overline{L_2}$, we therefore get that if $L_1$ and $L_2$ are decidable languages, then $L_1 - L_2$ is also decidable.


A more direct way to see this is to let $M_1$ and $M_2$ be Turing machines deciding $L_1$ and $L_2$, respectively and construct a Turing machine $M$ which accepts if and only if $M_1$ accepts and $M_2$ rejects. Then $M$ decides the language $L_1 - L_2$.

$\endgroup$
  • $\begingroup$ Isn't this a bit of a roundabout way of proving this? If you have $M_1,M_2$ deciding $L_1,L_2$, have $M$ accept exactly when $M_1$ accepts and $M_2$ rejects. $\endgroup$ – tomasz Mar 14 at 12:17
  • $\begingroup$ @tomasz I guess so, but the OP mentioned knowledge of closure under complement and intersection. I will add the more direct approach. $\endgroup$ – mrp Mar 14 at 13:11

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.