# How can the following language be determined in polynomial time

I'd love your help with understanding why the following is decidable and can be determinate in polynomial time ($L \in P$).

$L=\{(\langle M \rangle,w)|M$ is a Turing machine with Q states and one stripe and on running on $w$ it never moves left $\}$

I don't understand how we do that in polynomial time.

Thanks!

-
Your questions would be much better if you indicated a motivation and/or source for them. Why would you think you can do it in polynomial time to begin with? What have you tried? Where did you find the question? I have voted -1 because of the lack of this information. – Carl Mummert Aug 7 '12 at 13:18
It's form test that I'm trying to solve and have only final answers, without explanations. I haven't tried too much, it's not math. whether you know how to solve it or not. sometimes I'm trying to construct reductions and I have a direction, and you can sure read it in my questions. in my math questions I usually write all the way until I'm stuck. – Jozef Aug 7 '12 at 13:29

To answer your question about Xoff's correct answer, look at what $M$ is doing on input $w$. It begins by scanning $w$. While that's being simulated, we can check whether $M$ ever moves left, in which case we immediately reject $(\langle M \rangle, w)$. We'll get to the end of the input in no more than $|w|$ steps, after which we'll be looking at nothing but blank characters as input. Since we're still checking that $M$ only moves right, what gets written on the tape is immaterial, so our TM acts exactly as if it were a finite automaton with $|Q|$ states. That means that in no more than $|Q|$ more moves we'll have to repeat a state, which we can easily check. If $M$ hasn't moved left by then, it never will, so we again accept $(\langle M \rangle, w)$. We've taken no more than $|w|+|Q|$ moves to decide, as Xoff indicated.
Thank you for very clear and helpful explanation. "It begins by scanning w"- Does it mean that it only reads the string? so how could it move left it has to read $w$ from left to right? or is it reading and than might jump somewhere else? why doesn't it matter what's written on the stripe? I mean it might change the way the Turing machine simulates, no? – Jozef Aug 7 '12 at 15:57
For the question:"M visits some state more then one time?" would the answer be the same? $|w|+|Q|$? I'm trying to understand this method by another example. – Jozef Aug 7 '12 at 19:36
@Jozef. Then the problem is decided even quicker: simulate $M$ and at each step, record the state entered. If you repeat a state, accept, if not then there will be no more than $|Q|$ possible moves before you are guaranteed that $M$ will either halt or repeat a state. – Rick Decker Aug 8 '12 at 16:08
Just verify that you can accept $(M,w)$ after simulating $M$ on $w$ for $|w|+|Q|$ steps where $M$ only goes on the right.