# Is this language semidecidable?

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?

• Prove it the same way you prove any langauge is semi-decidable: by trying to describe a Turing machine that semi-decides it. – 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.