Sub language is not Turing-recognizable, or could it be?

Problem Detail: 

Let A and B be languages with A ⊆ B, and B is Turing-recognizable. Can A be not Turing-recognizable? If so, is there any example?

Asked By : Wilhelm

Answered By : Kaveh

This is something that confuses many students. The point here is that being subset of another language does not imply much about their difficulty of computation. You can always consider the trivial language $\emptyset$ and $\Sigma^*$ and any other language is between them w.r.t. set inclusion.

Therefore just knowing that a language contains or is contained in a easy to compute language doesn't say anything about the difficulty of computing it.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/1427