0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – André Nicolas
    Mar 4, 2014 at 5:00

1 Answer 1

Reset to default
1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ So in this case, all three are actually decidable because the L1 and L2 are decidable but that would not be the case if L1 and L2 where only recursively-enumerable? $\endgroup$
    – UndefinedReference
    Mar 4, 2014 at 5:16
  • $\begingroup$ 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. $\endgroup$
    – ajd
    Mar 4, 2014 at 5:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .