I recently started self studying about algorithms and decision problem, so I don't have a firm grasp on this particular area. In this context I found myself thinking about the following .

If $L_1$ is semidecidable and $L_2$ is decidable, what can one say about the language set defined by their difference $L_3 = L_1 \text{ \ }L_2$ ?

I'm inclined to believ that $L_3$ is semidecidable, but I can't think of a way to prove it.

Any ideas?

  • $\begingroup$ Prove it the same way you prove any langauge is semi-decidable: by trying to describe a Turing machine that semi-decides it. $\endgroup$ – David Richerby Oct 18 '15 at 17:47

If $L_1$ is semidecidable, there's a TM $M_1$ that takes a string $x$ and always reliably halts and answers "yes" if $x\in L_1$. If $L_2$ is decidable, there's a TM $M_2$ that always halts and reliably answers "yes" if $x\in L_2$ and "no" if $x\notin L_2$.

Make a new machine $M$ that when given an input string $x$ first runs $M_2(x)$. If the answer is "yes" then you know $x\notin L_1\setminus L_2$ so have $M$ halt and answer "no". If, on the other hand, $M_2(x) = "no"$ then $x$ may or may not be in $L_1\setminus L_2$, so then run $M_1(x)$ and do whatever $M_1$ does. It may never halt or it may answer "no", but if $x\in L_1\setminus L_2$ your $M$ will correctly answer "yes", proving that $L_1\setminus L_2$ is indeed semidecidable.

| cite | improve this answer | |

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.