# Given two languages $A,B \subseteq \Sigma^*$, prove that $A/B$ is semi-decidable if both the languages are semi-decidable

I have found two interesting questions regarding the quotient of languages, described as:

$$A/B=\{w \mid \exists z\in B\land wz\in A\}$$

The first one is:

Let $$A$$ and $$B$$ be regular languages, prove that $$A/B$$ is decidable By using the proof from this other question, it can be proved that $$A/B$$ is regular if $$A$$ is regular too.

Then, since any regular language is decidable, $$A/B$$ will be regular (and decidable) too.

The second one is:

Let $$A$$ and $$B$$ be semi-decidable languages, prove that $$A/B$$ is semi-decidable

Let us keep this in mind: $$w\in A/B \iff \exists z\in B: wz\in A$$

Since we are working with semi-decidable machines, then we have no problem iterating over all $$z$$'s until we find a good one!

Therefore, the idea to solve it will be the following: Let $$M_A$$ be the TM for $$A$$, and let $$M_B$$ be the TM for $$B$$.

We want to create a new TM for $$A/B$$ like so:(when given $$w$$ as input)

• Iterate through all $$z\in \Sigma^*$$
• For each such $$z$$, if both $$M_B(z)$$ and $$M_A(wz)$$ accepted, then accept.

Notice, that there is still an important detail left! What happens if $$M_B(z)$$ never stops? We will never continue to search the other $$z$$'s!

To solve that, we will modify the TM as follows:

• Let $$T=\{\}$$ be an empty set representing the set of all running "threads" we have created
• For $$z\in \Sigma^*$$:
• Create two new threads that will compute $$M_B(z)$$ and $$M_A(wz)$$ respectively. Add those two threads into $$T$$.
• Do one step in every thread in $$T$$.
• If at any point, there is some $$z$$ such that both threads $$M_B(z)$$ and $$M_A(wz)$$ have finished executing and both accepted, then accept as well.

This solution effectively runs the machine $$M_B(z_0)$$ (for a specific $$z_0$$) only one step for each new $$z$$ that we discover - instead of trying to run the machine until it halts. This allows us to continue to discover more new $$z$$'s even if the execution of those machines never ends!

I will leave it to you to verify that this machine really accepts $$A/B$$ :)