Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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|improve this question

2 Answers 2

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|improve this answer
1  
Thanks, I believe that is what I did in my comment to FrankW. –  nacho Mar 18 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|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}\}$. –  nacho Mar 18 at 0:48
    
I would have left out "starts with 01 and". But your suggestion works as well. –  FrankW Mar 18 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. –  nacho Mar 18 at 20:41

Your Answer

 
discard

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.