Language

$$

L_1 = {w in {0, 1 } ^ ast mid exists x in {0, 1 } ^ ast colon M_w (x) = x

$$

_{($ w $ is an encoding of a DTM, $ M_w $ is the respective DTM.)}

It's not decidable, according to Rice's theorem. However, it is recursively enumerable: a DTM simply chooses a $ x $ for which the condition is fulfilled in a non-deterministic manner.

Consider very similar language

$$

L_2 = {w in {0, 1 } ^ ast mid exists x in {0, 1 } ^ ast colon M_w (x) neq x }

$$

Rice's theorem argues that it is undecidable, but it is also not semi-decidable according to my sources.

Why can not we argue $ L_2 $ as we did for $ L_1 $, indicating that a DTM chooses the entry $ x $ in a non-deterministic way, the condition is fulfilled, $ L_2 in mathsf {RE} $?

The proof that $ L_2 not in mathsf {RE} $ performs the reduction $ overline H leq L_2 $, or $ H $ is the problem of stopping. I understand this proof by reduction, but it seems to me to contradict the argument of recursive enumerability that I give above.