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 believe that $L_3$ is semidecidable, but I can't think of a way to prove it.
Any ideas?
It is semidecidable. Look at it this way: it's the intersection of two languages, $L_1$ and $\overline L_2$ where $\overline L_2$ is the complement $L_2$. The complement of a decidable language is decidable, hence semi-decidable.
So it remains to show that the intersection of two semi-decidable languages is semi-decidable. Given TMs $M_1, M_2$, you can devise a TM $M$ which accepts the intersection of their languages:
On input $x$, $M$ simulates running $M_1$ and $M_2$ on input $x$, executing each of them one step at a time and alternating between them. If neither $M_i$ halts then $M$ also runs forever and doesn't accept $x$. Otherwise, one of the $M_i$ halts first and accepts $x$ – say, $M_1$ does. $M$ continues by running the other TM, $M_2$, step by step, exclusively. If $M_2$ halts then so does $M$, accepting $x$; otherwise, $M_2$ doesn't halt, it doesn't accept $x$, and $M$ will run forever too.
