"Let A be a finite alphabet, and let L1 and L2 be two Turing-recognisable languages over A such that L1 is a proper subset of L2, i.e. L1 ⊂ L2 but L1 ≠ L2. Let a language L over the alphabet A satisfy that L1 ⊂ L ⊂ L2. Does L have to be Turing-recognisable as well? Justify your answer." I am unsure about the answer to this question. My initial answer was yes, L has to be Turing-recognisable as well, because I couldn't find an example where it is not given that both L1 and L2 are, and L1 ⊂ L ⊂ L2.


1 Answer 1


Hint: consider the empty set and the set of all strings.

  • $\begingroup$ That kind of confuses me even more. I thought the empty set (ε) was not Turing-recognizable. Does A* (the set of all strings) contain ε as well? $\endgroup$
    – Mark
    Commented Apr 15 at 16:33
  • $\begingroup$ @Theo You are misunderstanding a few concepts here. $\varepsilon$ isn't the empty set, $\emptyset$ is. And $\emptyset$ is recognisable by a TM that simply rejects everything. $\varepsilon$ is the empty string, and is contained in $A^*$. $\endgroup$
    – Knogger
    Commented Apr 15 at 16:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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