The Gateway to Computer Science Excellence
0 votes
71 views

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.

in Theory of Computation by Boss (27.1k points) | 71 views
+1

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

0

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

+1
Works almost all the time, let's see if it works in gate !
0
Can I take the machine M2 to be the machine that accepts everything?
0
it accepts every string of length >= 0, using only $a$

Please log in or register to answer this question.

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,666 questions
56,157 answers
193,767 comments
93,740 users