Date: 29 Jun 2011 14:42
Number of posts: 3
RSS: New posts
A TM scans the same cell twice iff at some point the head moves to the left. We saw in exercise 5 question 1h, That if the head moves to the right for enough steps, The machine is bound to repeat a configuration (Hereby entering an infinite loop) which gurantees the head will never move to the left.
"enough steps" is of course polynomial in the length of the input. Again, See ex5 q1h.