# L = {⟨M⟩ : there does not exist w ∈$Σ^*$ such that M rejects w } is in coRE?

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

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