For an assignment I have to proof that for two given decidable languages A,B, A\B is decidable too.

My idea is as follows: If B is empty or doesnt have elements in common with A, then A\B is decidable because A\B=A.

If B is not empty and intersects with A, A\B is just a smaller subset of A and therefore decidable.

I have a feeling that this is either the wrong idea or not formalized enough. I would really appreciate any hints regarding that.

EDIT: A subset of a decidable language is NOT always decidable too, this was a misconception.

Thanks in advance

  • $\begingroup$ Why do you think a subset of a decidable language is still decidable? $\endgroup$
    – xskxzr
    Nov 10 '18 at 11:01
  • $\begingroup$ This is obviously a misconception, thanks for pointing that out. That leaves me with no useful approach to this assignment though. Can you point me in the right direction? $\endgroup$ Nov 10 '18 at 11:07
  • $\begingroup$ You can try to make use of the fact that $B$ is decidable. $\endgroup$
    – xskxzr
    Nov 10 '18 at 11:26
  • $\begingroup$ I can't think of any way to utilize that. Can you elaborate? $\endgroup$ Nov 10 '18 at 11:33

Let $M_A$ and $M_B$ be deciders for $A$ and $B$ respectively. You can construct a TM $M$,

$M$ = "On input x,

$\qquad$ 1. Simulate $M_A$ on x.

$\qquad$ 2. Reject if $M_A$ rejects. Else simulate $M_B$ on x.

$\qquad$ 3. Accept if $M_B$ rejects. Else reject."


$\qquad$ $M$ always halts as $M_A$ and $M_B$ always halts. $M$ accepts if $M_A$ accepts and $M_B$ rejects i.e, $x \in A$ and $x \notin B$. $M$ rejects otherwise.


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.