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
