# Turing Machines and Decidability

I saw this question in a textbook on decidable languages, and I was wondering how you would go about solving this type of question:

Assume L1 and L2 are decidable languages. Which of the following are decidable?

a. L1 Union L2

b. L1 Intersection L2

c. L1 - L2

I know that a decidable language is one that does not create a loop in a Turing machine and that it is Turing machine recognized, but I am not sure how to go about solving for these.

All I can think of, is that if a turing machine can decide L1 and L2, then a and b should be decidable but not c. Am I right or wrong?

Any explanation helps, thanks.

• For example, for the first, set two machines running, one a machine for $L_1$, the other for $L_2$. From given machines, producing a single machine is an unpleasant bit of coding, but it should be clear that it can be done. Mar 4, 2014 at 5:00

A decideable language is a language that can be recognized by a Turing machine that always halts. If you have Turing machines $P_1$ and $P_2$ that recognize $L_1$ and $L_2$, then you can recognize any language obtained by elementary set operations on $L_1$ and $L_2$ by running $P_1$ and $P_2$, obtaining their results, and then computing the appropriate Boolean function on their results. This applies to all three of the problems you state.
• All three are indeed decideable. If $L_1$ and $L_2$ are just recursively enumerable, then $L_1\cap L_2$ and $L_1\cup L_2$ are also recursively enumerable, but $L_1\setminus L_2$ is not necessarily recursively enumerable.