given this lanauge: $L=\left\{\langle M\rangle\right.$ : there does not exist $\mathrm{w} \in \Sigma^*$ such that M rejects $\left.\mathrm{w}\right\}$.

how can I determine whether it is in $R, R E \backslash R, \operatorname{coRE} \backslash R$, or $\overline{R E \cup c o R E}$?

I tried to prove the it is in $coRE\backslash R$, by reducing from the following language: $E_{T M}=\{\langle M\rangle: L(M)=\emptyset\}$ but I'm not sure I can iterate over $\Sigma^*$ where it might be infinite run on a Turing machine


1 Answer 1


$L$ is clearly not recursive: given a Turing machine $M$, consider $\overline{M}$ the machine where you reverse accepting and rejecting states.

Then it is clear that $\langle M\rangle\in E_{TM}$ if and only if $\langle \overline{M}\rangle \in L$.

However, $L$ is indeed in $coRE$, this can be proved by dovetailing: given a Turing machine $M$, the following algorithm will halt in finite time and answer correctly if $\langle M\rangle \notin L$, and never halts if $\langle M \rangle \in L$ (we consider inputs in lexicographic order for example):

n ← 1
while true:
    for i = 1 to n:
        simulate one more step of computation of M on the nth input;
        if it halts and rejects, then return false;
    n ← n + 1

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.