why is it taht for TM that can only read (cant write on tape) if its dosn't stop in less then |x|+|Q| steps it will not stop at all? where |x| is the size of the input x.
Date: 02 Jul 2010 03:58
Number of posts: 2
RSS: New posts
if it can only read it doesn't change the data on the tape, so the number of configurations is finite (for a given string).
since any config. is of the form w1-q-w2 there are no more then |Q|+|x| steps for the machine to stop
(otherwise, we went over the same kind of step, and we are in a loop)