question 4 part B moed a semester b 2008
guest (guest) 07 Aug 2012 22:07
L={<M>| M is a TM and for every input x, M does not pass the place ((|x|+1)/2) rounded up on the tape}
First of all, it is not clear which answer they highlighted as correct becuase both A. "the languages that can be decided in constant time" and B. "P" where colored yellow.
I don't get how it could be either of the two. How can we know that the for inputs of every length, the machine M won't pass the ((|x|+1)/2) rounded up on the tape? unless it is a machine that halts on the first step without moving the head or so? we've got at least aleph efes different palaces on the tape it must not pass for at least the same amount of inputs how is that decidable at all?
What am I missing?
