Decidability

Question

From http://www.cs.rice.edu/~nakhleh/COMP481/final_review_sp06_sol.pdf

 

$L_{26}=\{<M>|$ M is a TM such that both L(M) and $\lnot L(M)$ are infinite $\}$

I was unable to get proof given in pdf above.Can anyone explain, if someone got it.

Comments

Say, $M_1=\left \{a^n:n\,\,is\,\,a\,\,multiple\,\,of\,\,2\right \}$

$\overline{M_1}$ will be strings where n will not be multiple of 2

So, both $M_1$ and $\overline{M_1}$ are infinite. So, $L(M_1)=T_{yes}$

$M_2=\left \{a^n:n\geq 0\text{}\right \}$

$\overline{M_2}=\phi$

So, $M_1$ is infinite but $\overline{M_1}$ is not. So, $L(M_2)=T_{no}$

So, $T_{yes}\subset T_{no}$  as  $M_1\subset M_2$

So, it is a non-monotonous property. Hence non-RE

Correct me if I'm wrong

---

@Shobhit Joshi-Seems good to me :).But I can't detect any flaw here so be cautious.

---

Works almost all the time, let's see if it works in gate !

---

Can I take the machine M2 to be the machine that accepts everything?

---

it accepts every string of length >= 0, using only $a$