Is the following language in RE?

Given a language $$A \in RE$$, is the following language also in $$RE$$? $$L_{10}^{A} = \{ \langle M \rangle : \lvert A \cap L(M) \rvert \geq 10 \}$$ Where $$L(M) = \{x \in \{0, 1 \}^* \mid M \text{ accepts } x \}$$.

(I've managed to prove that if $$A \in R$$ then $$L_{10}^A \notin R$$ necessarily with a reduction from $$HALTING$$.)

While my intuition says it is in $$RE$$, I haven't been able to construct a turing machine that recognizes $$L_{10}^{A}$$ nor define a reduction from it to another language in $$RE$$.

And another challenge:

For every language $$A \in RE$$, show that there exists a language $$B_A \in R$$ such that for all $$x \in \{0, 1 \}^*$$ we have $$x \in A \iff \exists y \in \{0, 1\}^* : (x, y) \in B_A$$

All help with these two problems will be greatly appreciated.

Thanks.

$$L^A_{10}$$ is recursively enumerable. In particular, since $$A$$ is recursively enumerable, there is a Turing Machine $$M_A$$ that accepts $$A$$.

Let $$M^t$$ (resp. $$M_A^t$$) denote a Turing machine that simulates the first $$t$$ steps of $$M$$ (resp. $$M_A$$). If $$M$$ (resp. $$M_A$$) does not halt within $$t$$ steps, then $$M^t$$ (resp. $$M_A^t$$) halts and rejects.

For every $$M$$, $$|A \cap L(M)| \ge 10$$ if and only if there is some $$T$$ such that $$|L(M_A^T) \cap L(M^T)| \ge 10$$. Then you can accept $$L^A_{10}$$ as follows:

1. Start with $$t=1$$ and $$c=0$$;
2. Enumerate all words of length at most $$t$$ and, for each such word $$x$$:
• Run $$M_A^t$$ on $$x$$;
• Run $$M^t$$ on $$x$$;
• If $$x$$ is accepted by both $$M_A^t$$ and $$M^t$$, increment $$c$$ by $$1$$.
• If $$c \ge 10$$ halt and accept.
1. Double $$t$$, set $$c=0$$, and repeat from point 2.

In particular, the above Turing machine accepts $$M$$ when $$t \ge \max\{T, \ell\}$$, were $$\ell$$ is the length of the the tenth shortest word in $$L(M_A^t) \cap L(M^t)$$.

Regarding your second problem: let $$M$$ be a Turing machine that accepts $$A$$ and, for any word $$x \in A$$, let $$t_x$$ be the number of step executed by $$M$$ on input $$x$$.

Define $$B_A = \{ (x, 0^{t_x}) \mid x \in A \}$$, where $$0^{t_x}$$ denotes the word consisting of $$t_x$$ zeros. To decide whether $$(x, y) \in B_A$$ it suffices to simulate $$M$$ for (up to) $$|y|$$ steps. If $$M$$ takes exactly $$y$$ steps to accept, then accept. Otherwise reject.

• That is beautiful. Any ideas on the second problem? Commented Mar 23, 2022 at 14:05
• See my edited answer. Commented Mar 23, 2022 at 15:44