# Why is not language $L=\{w_i \mid w_{2i} \notin M_i\}$ recursively enumerable?

Why is not language $$L=\{w_i \mid w_{2i} \notin M_i\}$$ recursively enumerable? I need to show that by diagonalization, but dont know how? Its quite obvious for $L=\{w_i \mid w_i \notin M_i\}$, but for this I dont know how to show that. Thanks a lot!

EDIT: Mi is just Turing Automata with Godel's number i. wi and w2i are binary words

-
To make it possible for others to answer this question, you need to explain the notation - I assume $w_i$ is just a natural number, but what is $M_i$? Also, you should indicate the context in which you have encountered the question - is it in a class? What textbook are you using? What theorems do you know? – Carl Mummert Oct 29 '12 at 0:10
Thanks, i added little explanation, here is one of the sources for a topic ( cs.uwaterloo.ca/~watrous/360/handouts/diagonalization.pdf ). I am learning for exam. – Ondra Oct 29 '12 at 7:18

What you’ve written doesn’t quite make sense. First, what do you mean be $w_{2i}\in M_i$? $M_i$ is a Turing machine, not a set of binary words. I suspect that you really mean $w_{2i}\notin L(M_i)$, where $L(M_i)$ is the language of $M_i$. However, judging by the PDF, you probably want $w_{2i}\notin L(M_{w_i})$, not $w_{2i}\notin L(M_i)$.

Assuming these changes, look at page $4$ of the PDF. If you replace the diagonal of the table, which corresponds to the pairs $\langle M_{w_i},w_i\rangle$, with the set of entries corresponding to the pairs $\langle M_{w_i},w_{2i}\rangle$, you’ll still be looking at a set of entries having exactly one entry in each row. If you invert all of the entries in those positions by changing $1$’s to $0$’s and vice versa, the reasoning at the bottom of the page applies. After this flipping, the entry in position $\langle M_{w_i},w_{2i}\rangle$ is $1$ if and only if $w_{2i}\notin L(M_{w_i})$, so the language consisting of those words $w_{2i}$ such that the flipped $\langle M_i,w_{2i}\rangle$ is $1$ is exactly the language $L=\{w_{2i}:w_{2i}\notin L(M_{w_i})\}$. Just as in the example in the PDF, for each $i\in\Bbb N$ $L$ differs from $L(M_{w_i})$ in column $w_{2i}$: if $w_{2i}\in L$, the flipped $\langle M_i,w_{2i}\rangle$ entry in the table is $1$, the original $\langle M_i,w_{2i}\rangle$ entry is therefore $0$, and $w_{2i}\notin L(M_i)$, while if $w_{2i}\notin L$, then $w_{2i}\in L(M_i)$. This shows that $L$ is not $L(M_i)$ for any $i$ and hence that $L$ is not r.e.

-
Great, that was the trick I was lookig for! Sorry for bad formulation. – Ondra Oct 29 '12 at 10:53