Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.


share|cite|improve this question
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
up vote 1 down vote accepted

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.

share|cite|improve this answer
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
@Jozef. Remember, if the machine only moves right, it will never return to the cell it left, so what was written on the cell can have no possible influence on subsequent moves, meaning that we can essentially ignore whatever was written by the TM. – Rick Decker Aug 7 '12 at 16:09
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. Are we still considering TMs that only move right? – Rick Decker Aug 8 '12 at 0:11
@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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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