# Determining whether the problem of given a turing machine figuring out whether the language it accepts is the set of prime length inputs is R.E

I'm trying to figure out whether the following problem is R.E.?

Given a turing machine $$M$$ with alphabet $$\Sigma$$ is it the case that:

$$L(M) = \{w \in \Sigma^* | |w| \space is \space prime\}$$

I think I have a reduction from $$HALT$$ complement which is co - R.E. to the problem proving that it's not R.E. but I'm not entirely sure if it's correct (Define a new turing machine which on input y runs M on w for |y| steps and rejects if M halts on w in |y| steps, else perform sieve and accept iff |y| is prime) but I'm not sure if this is correct.

• Can you copy and paste the definition of "R.E" that is used in this question? Commented Jun 8, 2022 at 1:22
• A R.E.language is a language for which there exists a Turing machine (doesn't have to be a total Turing machine) accepting it Commented Jun 8, 2022 at 6:13

I think your reduction is correct. Indeed, the reduction is clearly computable and furthermore if the original Turing machine $$M$$ halts on (the fixed) input $$w$$, then the set of words accepted by the new Turing machine $$M'$$ is a finite set of words (of prime length), while if $$M$$ does not halt on input $$w$$, then the words accepted by $$M'$$ are precisely those words which have prime length. Thus your problem is $$coRE$$-hard.
Let me also point out that it is in fact even harder than $$coRE$$-hard: it is $$coRE^{RE}$$-complete (here $$coRE^{RE}$$ is the complement of languages that can be enumerated by a Turing machine that has an oracle to the halting problem). The lower bound can be proved by reducing the following $$coRE^{RE}$$-hard problem to it: given a Turing machine $$M$$, determine whether it halts on every input. The reduction is very similar to the reduction that you already used. On input $$w$$, our Turing machine $$M'$$ simulates the given Turing machine $$M$$ on every input of length $$|w|$$, and if $$M$$ halts on every such input, then $$M'$$ accepts iff $$|w|$$ is prime.