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?

$\endgroup$
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.

$\endgroup$
  • $\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 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 at 12:39
  • $\begingroup$ Yes, good catch. It should be "does not halt". (The halting problem is R.E.) Fixed. $\endgroup$ – dkaeae May 21 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 at 12:43

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.