1
$\begingroup$

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.

$\endgroup$

1 Answer 1

2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ That is beautiful. Any ideas on the second problem? $\endgroup$ Commented Mar 23, 2022 at 14:05
  • 1
    $\begingroup$ See my edited answer. $\endgroup$
    – Steven
    Commented Mar 23, 2022 at 15:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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