Deteremine if $L = \{\langle M\rangle : L(M) \text{ consits of all words of prime length}\}$ is in $R$ or in $RE\setminus R$ or not in $RE$

I am trying to prove that $L$ is not in $RE$ by reduction from $L_{acc}^c = \{M,w: w\notin L(M)\}$ to $L$, but I it seems not works for one side and I have no idea how can I fix it.

if $x=\langle M,w\rangle$ in $L_{acc}^c$ then for any input $z$, I will check if $|z|$ is prime (it can be done by TM) and if it is, then my machine says yes. if not then we will run $M$ on $w$ and answer what we got. In this situation our language will consist of all the words with prime length.

but in the following way we have an issue since our language will be all the words, i.e $\Sigma^*$

If $x=\langle M,w\rangle$ not in $L_{acc}^c$ then for any input $z$ our machine will say yes since if $|z|$ is prime we say yes and if not then $w\in L(M)$ and therefore we say yes, so we say yes for any input. and that cant work since we need to prove that $f(x)\notin L$ to out reduction work.

I have no idea how to fix the this, any ideas?


1 Answer 1


The "key" here is to make $f$ construct a new machine $M'$ that will contain all of the primes assuming that $w\notin L(M)$, and otherwise, there will be at least one prime it rejects.

Now, the reduction $f$ will work by taking $\langle M, w\rangle$ and outputting the following TM $M'$:

  1. On input $z$, run the following:
  2. Emulate $M$ on $w$ for $|z|$ steps.
  3. Accept if $M$ didn't halt in time, or if $M$ rejected $w$.

Clearly, if $w\notin L(M)$ then $L(M')=\Sigma^*$, hence $\langle M'\rangle$ is in the language you reducte to. However, if $w\in L(M)$, then there is some positive number $t\in \mathbb{N}$ such that $M$ accepted $w$ in $t$ steps. Therefore, $M'$ will reject all inputs $z$ with $|z|>t$. In particular, since there are an infinite number of primes, there is some prime $p$ with $p>t$. Then, choose some word $v$ with $|v|=p$, and viola! $v\notin L(M')$, hence $\langle M'\rangle $ is not in the language you reduce to, since it doesn't contain all words with prime length.

  • $\begingroup$ I like your solution! may I ask what was your intuition for that solution? how did you came to it? Toda :) $\endgroup$
    – John D
    Jul 20, 2021 at 19:15
  • 1
    $\begingroup$ @JohnD It is a common "trick" when using reductions from $L_{acc}^c$ to other languages. Coming up with it is a matter of knowing it and remembering how to use it :) Bevakasha! $\endgroup$
    – nir shahar
    Jul 20, 2021 at 19:49

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.