10
$\begingroup$

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?

$\endgroup$

4 Answers 4

18
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ But I can't find any subset language of Σ∗ that is non-Turing-recognizable. $\endgroup$
    – gfe
    Apr 22, 2012 at 18:01
  • 3
    $\begingroup$ @Wilhelm, take any language that is not Turing-recognizable and it will work. $\endgroup$
    – Kaveh
    Apr 22, 2012 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, 2012 at 20:24
  • $\begingroup$ @Wilhelm, yes. :) $\endgroup$
    – Kaveh
    Apr 22, 2012 at 20:33
1
$\begingroup$

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.

$\endgroup$
2
  • $\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, 2014 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, 2014 at 17:48
-2
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ Yes, it is wrong: an acceptor for a language must not accept any words except those in the language. $\endgroup$ Jul 11, 2012 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, 2012 at 14:36
-4
$\begingroup$

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.. =)

$\endgroup$
1
  • 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, 2012 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.