Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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

1 Answer 1

up vote 3 down vote accepted

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.

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.