0
$\begingroup$

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

  • 0
    Thanks, i added little explanation, here is one of the sources for a topic ( https://cs.uwaterloo.ca/~watrous/360/handouts/diagonalization.pdf ). I am learning for exam.2012-10-29

1 Answers 1

4

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.

  • 0
    Great, that was the trick I was lookig for! Sorry for bad formulation.2012-10-29