0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Can you copy and paste the definition of "R.E" that is used in this question? $\endgroup$
    – John L.
    Commented Jun 8, 2022 at 1:22
  • $\begingroup$ 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 $\endgroup$ Commented Jun 8, 2022 at 6:13

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

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.