# 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!

#### Solutions Collecting From Web of "How can the following language be determined in polynomial time"

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.

Just verify that you can accept $(M,w)$ after simulating $M$ on $w$ for $|w|+|Q|$ steps where $M$ only goes on the right.