# Sandwiching Languages

I am studying for my algorithms final and came across the following problem:

Find three languages $L_1 \subset L_2 \subset L_3$ over the same alphabet such that $L_2 \in P$ and $L_1,L_3$ are undecidable.

I am having trouble coming up with an example of three such languages. My first thought was to use a form of the halting problem for both $L_1$ and $L_3$ since that is pretty much the only undecidable language I know and am familiar with. I was thinking of perhaps coming up with something of the form \begin{align*} L_1 &= \{M \mid \text{$M$ is a Turing machine that starts with 00 and halts}\}\\ L_2 &= \{M \mid \text{$M$ is a Turing machine that starts with a 00}\}\\ L_3 &= ? \end{align*} but this doesn't seem to be working. Any ideas are appreciated!

Hint: Let $L_3 = L_2 \cup M$, where $M$ is a language similar to $L_1$ and disjoint from $L_2$.

• Thanks, I believe that is what I did in my comment to FrankW. Mar 18, 2014 at 0:49

Hint: Your approach can be completed and you need to change only one word in the description of $L_1$ to get a description for $L_3$ that works.

• I am not sure if I see what word I should change, but I might have solved it anyway. Let $L_1,L_2$ be defined as above. Then simply define $L_3 = \{M \mid M \text{ is a Turing machine that starts with 00, or starts with 01 and halts}\}$. Mar 18, 2014 at 0:48
• I would have left out "starts with 01 and". But your suggestion works as well. Mar 18, 2014 at 1:14
• Yup. I would also like to leave a note for posterity's sake that using two bits in the beginning is unnecessary, just using one bit does indeed achieve what I need. Mar 18, 2014 at 20:41