Can someone help me go over that the following language can be recognized by a Turing Machine?

$$L = \{\langle M,w\rangle \mid M \text{ accepts a prefix of } w\}$$

We can construct a universal Turing Machine $U$ that recognizes $L$. $U$ can be constructed as follows:

$U$: On input $\langle M,w\rangle$

  1. Simulate $M$ on $w$.
  2. If M accepts, $U$ accepts. Otherwise, $U$ rejects.

This seems a bit too simple so I wanted to ask how I can go about the construction of $U$.

  • 2
    $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – David Richerby Feb 27 '16 at 4:07
  • 2
    $\begingroup$ Having said that, your answer can't possibly be correct because it has nothing to do with prefixes. $\endgroup$ – David Richerby Feb 27 '16 at 4:08
  • $\begingroup$ @DavidRicherby Thanks for pointing that out. I've edited my question accordingly. Another way that I was thinking about going about this was to build a modified TM M' such that M' would accept a prefix of w (say we call it v) and then v concatenated with any other string would from w. But I don't know if that helps much. $\endgroup$ – firesage123 Feb 27 '16 at 4:13

As pointed out by David Richerby, you need to generate all the prefixes first.

Correct solution would be:

U: "On input <M,w>" 

1. Generate all prefixes of w non-deterministically 
   (by blanking the input word after the prefix)
2. Simulate M on w (non-deterministically again).
3. If M accepts, U accepts. 
   Otherwise, if M rejects then U rejects. 
   And if M loops then U also loops.

And as to your question, "How you will go about constructing $U$?", it is just a modified Universal Turing Machine.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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