I have a problem that I have no idea how to approach. I've been looking at using mapping reductions, but I can't find a way to apply it.

Assume some alphabet $\Sigma$ and two languages $A, B \subseteq \Sigma^*$.

Define the language $A / B = \{x \in \Sigma^* \mid xy \in A \text{ for some } y \in B \}$.

Prove that if both $A$ and $B$ are recursively enumerable then also $A / B$ is recursively enumerable.

(The term recursively enumerable is also called semi-decidable and Turing recognizable).

  • 2
    $\begingroup$ What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$ – D.W. May 17 '17 at 16:37
  • 2
    $\begingroup$ Try applying the definition of recursively enumerable, and spend some time thinking about it. You might also want to re-read your textbook or lecture notes; I imagine the techniques shown there will be enough to solve this exercise. $\endgroup$ – D.W. May 17 '17 at 16:38
  • $\begingroup$ If $A$ and $B$ are recursively enumerable, then so is $A \times B$? $\endgroup$ – Thumbnail May 18 '17 at 9:12

Recursively enumerable languages can equivalently be defined as languages of the following form:

$$ x \in L \longleftrightarrow \exists y R(x,y), $$ where $R$ is a computable relation.

Let $R_A,R_B$ be the relations demonstrating that $A,B$ are recursively enumerable. Then

$$ \begin{align*} x \in A/B &\longleftrightarrow \exists y . y \in B \land xy \in A \\ &\longleftrightarrow \exists y,z,w. R_B(y,z) \land R_A(xy,w). \end{align*} $$

You take it from here.


It is straight-forward to construct a semi-decider for $A / B$: given $x$, search for $y \in B$ so that $xy \in A$.

Since all three subcomputations, namely

  • enumerate all $y$,
  • check if $y \in B$, and
  • check if $xy \in B$

are partially recursive, you'll have to interleave all these computations in a clever way. I'll leave you to figure out the details.

Buzzwords to search for are time sharing and dovetailing.


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.