# Is it possible to prove closure of decidable languages under union and intersection, using enumerators?

We can use multi-tape enumerators. (Of course it is not valid to use turing machines albeit the fact that any enumerator has an equivalent TM)

What we need is to prove that if $A$ and $B$ are decidable then $A\cup B$ and $A\cap B$ are also decidable.

Can it be done? If so, what is a possible approach?

• Why is not valid to use a TM as enumerator? What do you mean by "enumerator"? – fade2black Sep 15 '17 at 7:27
• "Loosely defined, an Enumerator is a Turing Machine with an attached printer. It can use that printer as an output device to print strings. Evety time the Turing machine wants to add a string to the list, it sends the string to the printer." from the textbook "Introduction to the Theory of Computation" by Michael Sipser, page 180. – Joezer Sep 15 '17 at 7:55
• You can do it using two tape TM, tape 1 is the work tape, and tape 2 is the output tape (printer). You print output strings on the tape 2 by separating them by a single blank. My answer is still valid. – fade2black Sep 15 '17 at 7:59

Given a decidable language $L$ consider the following enumerator:

EnumL
loop on strings x over 0 and 1 in canonical/lexicographic order
if x in L then print x
end
end


This procedure enumerates/emits all strings in $L$ in lexicographic order. So you can decide if $x \in L$ by running EnumL until it prints the first string of length $|x| + 1$. If it does print $x$ until that time then it means $x \in L$, otherwise $x \notin L$. Thus, using both enumerators EnumA and EnumB you can decide $x \in A\cup B$ and $x \in A\cap B$. In other words, if one of EnumA or EnumB eventually emits $x$ then $x \in A\cup B$, and if both EnumA and EnumB emit $x$ then $x \in A\cap B$.