[Solved]: Sandwiching Languages

Problem Detail: 

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!

Asked By : kbrose

Answered By : Yuval Filmus

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/22735