-1
$\begingroup$

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!

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ 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. $\endgroup$
    – David Richerby
    Jun 16, 2016 at 10:09
  • $\begingroup$ 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. $\endgroup$
    – user53679
    Jun 16, 2016 at 10:35
  • 1
    $\begingroup$ 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. $\endgroup$
    – David Richerby
    Jun 16, 2016 at 11:31
  • $\begingroup$ 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! $\endgroup$
    – Raphael ♦
    Jun 18, 2016 at 22:26
  • $\begingroup$ 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. $\endgroup$
    – Raphael ♦
    Jun 18, 2016 at 22:27

1 Answer 1

Reset to default
2
$\begingroup$

I would go this way:

  1. Assume that the language $L ⊆ \Sigma^*$ is decidable by a TM M.
  2. Build a TM M' that decides L1 by relying on M.
  3. Build a TM M'' that decides L2 by relying on M.
  4. State that by having assumed L decidable than L1 and L2 have become decidable as well.

M' and M'' will perform some operation (e.g. compute one or more prefixes v of the word w of increasing length), simulate M on v (as a Universal TM does with other TMs) and decide.

It should be sufficient to provide an informal description of what M' and M'' do and a diagram as the following: diagram The diagram shows how to build a TM M1 relying on M: M1 does some operation (a copy) and then calls M (a TM it is supposed to exist).

Of course it is important that the "extra" operations performed by M' and M'' before calling M (those on computing prefixes) must be reasonably decidable.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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