1
$\begingroup$

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!

  • 0
    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.2012-08-07

2 Answers 2

1

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.

  • 0
    @Jozef. That's an undecidable problem. Post it in a question and you'll surely get an answer.2012-08-10
3

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