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?


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.

  • $\begingroup$ But I can't find any subset language of Σ∗ that is non-Turing-recognizable. $\endgroup$ – gfe Apr 22 '12 at 18:01
  • 3
    $\begingroup$ @Wilhelm, take any language that is not Turing-recognizable and it will work. $\endgroup$ – Kaveh Apr 22 '12 at 19:07
  • $\begingroup$ I see, so I can use the halting problem to prove that there is such a language. $\endgroup$ – gfe Apr 22 '12 at 20:24
  • $\begingroup$ @Wilhelm, yes. :) $\endgroup$ – Kaveh Apr 22 '12 at 20:33

When a Turing-recognizable language $X$ is not decidable, it implies that it is not co-Turing-recognizable (in other words: $X^c$ is not recognizable). Since $X^c$ is a perfectly valid subset of $\Sigma^*$, this supports the fact that for a language $A \subseteq B$ where $B$ is Turing-recognizable, $A$ may very well not be.

  • $\begingroup$ I think Kaveh's answer is better and more to the point. Any language is a subset of $\Sigma^*$ and we know that $\Sigma^*$ is decidable and that there are arbitrarily hard languages. $\endgroup$ – Pål GD Apr 6 '14 at 19:48
  • $\begingroup$ That's what I tried to explain, as $X$ could be any language, because $X \subset \Sigma^*$ automatically holds. ;) $\endgroup$ – Sander Apr 7 '14 at 17:48

Your discussion successfully confused me :(

"Can A be not Turing-recognizable?"

I feel A is always Turing-recognizable. Here is my thinking,

Since B is Turing Recognizable => There is some TM which accepts all the words of language B => There is a TM which accepts (all the words of language A + some other words) => There is a TM which accepts all the words of language A => A is Turing Recognizable.

Is this wrong? Can there be any case where A is Non-TRL while B is TRL. Kindly help

  • 1
    $\begingroup$ Yes, it is wrong: an acceptor for a language must not accept any words except those in the language. $\endgroup$ – reinierpost Jul 11 '12 at 14:18
  • $\begingroup$ Please don't post follow-up questions as answers. Use comments (after you have proven to the system that you are trustworthy) or create a new post if the new question is significantly different (not the case here). $\endgroup$ – Raphael Jul 17 '12 at 14:36

In this case A couldn't be Turing-recognizable. Take this as an example:

language B is the union of a language t.r (C) and a language not t.r(A). you can create a turing machine that recognizes B. A is not t.r and A ⊆ B.

is that right? i dont know if it is..so.. =)

  • 3
    $\begingroup$ not every union of $C\in RE$ and $A\notin RE$ is recognizable. For instance, let $C=\emptyset$ and $A$ the halting problem. You cannot create a turing machine that recognizes $B=A \cup C$. $\endgroup$ – Ran G. Apr 22 '12 at 7:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.