A language which is neither r.e. nor co-r.e

Question

First, consider $$L_\exists=\{\langle M\rangle \mid M \text{ is a Turing machine and accepts some input}\}$$ is RE. I tried to construct a Turing machine:

Input: Code(M);
L_e_TM(Code(M))
    for all words w of binary strings
        simulate M on w, 
            if M accept w then return true;
    end for
end

Since we do not have to care about whether it halts or not, so we can use it to recognize $L_1$. But surely, this is language is not recursive which can be shown by reduction from the halting problem or by Rice's theorem. But when we consider the complement of this language (for simplicity, we think all binary strings are valid Turing machine codes, otherwise we can just add a decider to check whether it is one recursively which will not affect the main result), $$L_{\emptyset}:=L_\exists^\complement=\{\langle M\rangle \mid M \text{ is a Turing machine and accepts no input}\}.$$ Similar we can just change the code above inside the for-loop:if M accept w then return false. Then both are in RE. Then they are in R? What was wrong? I thought there must be something wrong with the Turing machine code, but we are not talking about recursiveness, so I don't think the machine will not do the job to check whether it is in $L_\exists$ or not. Somewhere, I have seen $L_\exists$ is RE. Hence,

Furthermore, consider

$$L_\forall=\{\langle M\rangle \mid M \text{ is a Turing machine and accepts all inputs}\}$$ and $$L_\forall^\complement=\{\langle M\rangle \mid M \text{ is a Turing machine and accepts not all inputs}\}.$$ Are they both non-RE or one is RE and the other not?

Answer 1

Recall that a language is r.e. iff its complement is co-r.e. It follows that a language is neither r.e. nor co-r.e. iff its complement is neither r.e nor co-r.e., just like a language is recursive iff its complement is.

The language $L_{\exists}$ is recursively enumerable, though not recursive. To enumerate it, simulate all Turing machines on all possible inputs, and output a Turing machine whenever it halts on some inputs. To see that it's not recursive, reduce the halting problem to it.

Your other example $L_{\forall}$, usually known as TOT, is indeed neither r.e. nor co-r.e. In fact, it is $\Pi_2$-complete. You can prove that it is neither r.e. nor co-r.e. directly, by finding appropriate reductions from the halting problem.