toc

Question

10. Consider the following languages:
L
ne = {〈M〉│L(M) ≠ ф }
L
e = {〈M〉│L(M) = ф }
where 〈M〉 denotes encoding of a Turning machine M
Then which one of the following is true?
(a) Lne is r.e. but not recursive and Le is not r.e.
(b) Both are not r.e.
(c) Both are recursive
(d) Le is r.e. but not recursive and Lne is not r.e.

Comments

Le = {〈M〉│L(M) = ф } use Rice second theorem.

Tyes=ф and Tno= sigma^* 

so here Tyes is subset of Tno so it is non.re 

Lne = {〈M〉│L(M) ≠ ф } is the complement of above language and we know that complement of non.re is also non.re .

So from this we can say that both the languages are non recursively enumerable.

---

2nd one is not a complement of 1st .

1st one is RE, but not recursive.

---

@kapilp what is the solution of this question??

---

1st one is RE, but not recursive.

2nd one is even not RE.

Answer 1

e : M accept ф is not R.E because we can't have have turing machine that accept nothing...

ne: M does not accept ф ,we can have Turing machine that accept something , may be i can go in infinite loop but we have enumeration procedure for this, Hence  it is R.E

so (a) will be the answer

u can see : https://www.youtube.com/watch?v=8TuLr0cggMY&index=95&list=PLK_sH5jbkYciCyOTllsGyHVcHErHhtnZZ#t=04m45s