Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
up vote 3 down vote accepted

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

share|cite|improve this answer
Thanks, I believe that is what I did in my comment to FrankW. – kbrose Mar 18 '14 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.

share|cite|improve this answer
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}\}$. – kbrose Mar 18 '14 at 0:48
I would have left out "starts with 01 and". But your suggestion works as well. – FrankW Mar 18 '14 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. – kbrose Mar 18 '14 at 20:41

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.