0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Why is not valid to use a TM as enumerator? What do you mean by "enumerator"? $\endgroup$ – fade2black Sep 15 '17 at 7:27
  • 1
    $\begingroup$ "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. $\endgroup$ – Joezer Sep 15 '17 at 7:55
  • 1
    $\begingroup$ 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. $\endgroup$ – fade2black Sep 15 '17 at 7:59
2
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

Please be careful:

A language is recursively enumerable iff there exists an enumerator that lists its elements.

We cannot use an enumerator to handle decidable languages except if we require additional properties. A language is decidable iff either of the following

  • there exists an enumerator that lists the strings in lexicographic order

  • there exist enumerators [in any order] for both the language and its complement.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.