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.
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.
This is in contrast to the case for ''recursively-enumerable'' languages, which may not be recognizable by a Turing machine that always halts; the Turing machine is only required to halt when it is given a string in the language. Thus arguments of the form "run both machines and then do something" don't work (out of the box) because one or both of the machines may never stop.