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.


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.