Doubt - TOC

Question

State True/False

A subset of recursive language can be recursive enumerable that is not recursive.

P.S : I don't know the answer.. but it should be false according to me.. Kindly let me know if i am wrong with an example ..

Answer 1

Take the universal set of all strings over an alphabet set - which is regular and hence recursive. Now, the question reduces to does there exist any recursively enumerable langauge which is not recursive? I guess you know the answer- an example is language of Halting problem.

Comments

$\text{sir it means if there does exists some language }\,L\, \text{subset}\,of \sum ^{*} \,\text{which is recursive enumerable but not recursive}$.

---

$\text{if there no such language exists,then halting problem will be decidable},$ $\text{hence contradiction. Am i right sir?}$

---

I just meant that halting problem is a r.e. one but not recursive and this every one knows and hence no proof is needed.

---

okk sir.