why $L=\{\langle M\rangle\mid M \text{ is a TM that accepts all even number}\} \notin \text{RE}$ [closed]

Question

$L=\{\langle M\rangle \mid M \text{ is a TM that accepts all even number}\}$ hello everyone I anderstennd why $L\in \text{coRE} $ b but I don't understand why $ L\notin \text{RE}$

I Have proved that $ L\in \text{RE}$ by $HP \le L$ by the the following reducing function:

$f(\langle M,x\rangle) = \langle M_x\rangle$

$M_x$ on the input $y$:

1. Simulate $M$ on $x$.
2. accepts

validation of the reduce function:

• if $\langle M,x\rangle\in HP$: $M$ halts on every input $x$, $M_x$ simulate $M$ on $x$, then $M_x$ accepts, meaning: $M_x$ accepts every input y and particular every even number, meaning $|L(M_x)|=\infty$ so $\langle M_x\rangle \in L$
• if $\langle M,x\rangle\notin HP$: $M$ doesn't halts on input $x$, $M_x$ simulate $M$ on $x$, then $M_x$ get to forever loop, meaning: $M_x$ doesn't accepts every input y and particular every even number, meaning $|L(M_x)|=0$, so $\langle M_x\rangle \notin L$

because I know $L \notin \text{RE} $ I assume the reduce function I wrote here is wrong, can anyone explain me why?

thank in advanced :)

Answer 1

You have made an error. One cannot prove that a set is computably enumerable by reducing the halting problem to it. That would be like trying to show that someone is short by proving that they are at least as tall as a particular short person. After all, even very tall people are at least as tall as your given short person. Similarly, we cannot deduce that a set is simple by reducing a simple set to it, since even very complicated sets will have that feature. The halting problem reduces to sets of arbitrarily high complexity, since $0'\leq_T 0'\oplus A$ for any set $A$, but this doesn't mean that those sets are simple.

So that was the error in your proof. But meanwhile, let me help to analyze the complexity of your set by finding the exact complexity. I claim that your set $L$ is $\Pi^0_2$ complete, and therefore it is exactly equivalent to the double jump $0''$, which is the halting problem relativized to an oracle for the usual halting problem. Specifically, it is easy to see that $L$ has complexity $\forall\exists$, since $M$ is in $L$ just in case every even number input leads to an accepting computation, which is a $\forall\exists$ statement. Convesely, consider any $\forall\exists$ statement $\forall n\exists m\,\varphi(n,m)$, where $\varphi$ has only bounded quantifiers. We can create a machine $M$ that on input $2n$ searches for an $m$ for which $\varphi(n,m)$, accepting $2n$ when such an $m$ is found. Thus, the statement is true if and only if $M\in L$. So we have reduced $\Pi^0_2$ truth to $L$, and so it is $\Pi^0_2$-complete.