patternModerate
Sub language is not Turing-recognizable, or could it be?
Viewed 0 times
subrecognizablecouldlanguageturingnot
Problem
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#1427, answer score: 18
Revisions (0)
No revisions yet.