# Turing Machine and decidability

so the thing is that i have to prove that if the language $L ⊆ \Sigma^*$ is decidable then both languages are also decidable. $$P_1(L) = \{w ∈ Σ\mid \text{ For every prefix v of w, we have }v ∈ L\},$$ $$P_2(L) = \{w ∈ Σ\mid \text{ There's a prefix v of w, so that }v ∈ L\}.$$

My idea is to create two TM for $P_1$ and $P_2$ and prove that they're decidable, but I don't know if it's right or not, and even if it is I have no clue how to proceed. I would be thankful for every help or tip!

• Yes, the simplest way of proving that any language is decidable is usually to demonstrate a TM that decides it. To proceed, try to think of an algorithm to solve the problem in pseudocode or your favourite programming language. Then try to describe it in terms that make it easier to implement as a Turing machine. Jun 16, 2016 at 10:09
• Tht thing is that what i'm supposed to do is only a description of the needed machines, what do they do? what happens on thr tapes? etc. Jun 16, 2016 at 10:35
• OK -- that's good because actually writing down the definition of a Turing machine in terms of its states and transition function is a real pain. But still, starting with an algorithm "for an ordinary computer" is the best way -- then you can figure out how you'd implement that on a Turing machine by describing how the heads would move around and change the tape contents. Jun 16, 2016 at 11:31
• Welcome to Computer Science! The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you!
– Raphael
Jun 18, 2016 at 22:26
• What specifically have you tried? Where did you get stuck? We do not want to just do your (home-)work for you; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? You may also want to check out our reference questions.
– Raphael
Jun 18, 2016 at 22:27

1. Assume that the language $L ⊆ \Sigma^*$ is decidable by a TM M.