1
$\begingroup$

Let $L_{1},L_{2}$ be languages that are not Turing recognizable, and let $L$ be a language such that $L_{1} \subseteq L \subseteq L_{2}$.

Is $L$ also not Turing recognizable?

I am inclined to believe it is, but I really have no idea how to show this. It seems that non-recognizable languages have very little about them that could be used to solve a problem like this. Ideas?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

The answer is no, of course.

Consider, for instance, the following languages:

  • $L_1 = \{ \langle M \rangle \# \langle M \rangle \mid \, \text{$M$ is a TM which does not halt on input $\langle M \rangle$} \}$
  • $L = \{ \langle M \rangle \# \langle M \rangle \mid \, \text{$M$ is a TM} \}$
  • $L_2 = L \cup \{ \langle M \rangle \# w \mid \, \text{$M$ is a TM which does not halt on input $w$} \}$

Then it is easy to see neither $L_1$ nor $L_2$ are recursively enumerable (i.e., Turing-recognizable), despite $L$ being even context-sensitive. (In fact, you could even make $L$ context-free by replacing the second $\langle M \rangle$ with its reversed copy.)

The upshot is that set inclusion (on its own) tells us very little about the sets involved being recursively enumerable or not, unless the symmetric difference between them is finite. In the case of $L_1 \subseteq L \subseteq L_2$, we do know, for instance, that $|L \setminus L_1|$ or $|L_2 \setminus L|$ being finite implies that $L_2$ is also not recursively enumerable.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Excellent answer! I am insanely curious as to how you came up with those machines. What thought process led you to those particular constructions? It seems like something I couldn't have come up with myself. $\endgroup$
    – user308485
    May 21, 2019 at 12:37
  • $\begingroup$ Also, isn't $L_{1}$ Turing-recognizable? Shouldn't you be using the complements of these languages? $\endgroup$
    – user308485
    May 21, 2019 at 12:39
  • $\begingroup$ Yes, good catch. It should be "does not halt". (The halting problem is R.E.) Fixed. $\endgroup$
    – dkaeae
    May 21, 2019 at 12:41
  • $\begingroup$ To answer your first question: These are all pretty basic variants of the halting problem. Then you just need to "tweak" things so you get the set inclusions you need (e.g., setting $L_2 = L \cup \cdots$). $\endgroup$
    – dkaeae
    May 21, 2019 at 12:43

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.