Question: In the proof of Theorem we ignored one fine point. When a configuration grows, the rest of the tape's contents have to be moved. Does this oversight affect the conclusion?
Theorem: Suppose that a nondeterministic Turing machine M can carry out a computation in n steps. Then a standard Turing machine can carry out the same computation in O (kan) steps, where k and a are independent of n.