(goal): For some c, for all words w accepted with length n ( number of steps is bounded by c^(1+p(n)).
Proof is a pumping lemma style proof. If it takes too long to accept
a word of length n then the ID must repeat and so there must be a shorter
accepting sequence.
Key thought: if word w has n symbols then the tape available is p(n) long.
So how many different tapes are there with p(n) symbols
each with t =|\Gamma| possibilities.
Answer: t^(p(n)).
Where can the head be? Anywhere in the p(n) tape symbols.
And assume: s= |Q| -- the number of states.
Then only s*p(n)* t^(p(n)) possible IDs.
Trick: set c=s+t and look at c^(1+p(n)).
Prove it is > s*p(n)* t^(p(n)).
Hence within c^(1+p(n)) steps an ID must repeat. So it either
accepts earlier or not all in p(n) space.