2
$\begingroup$

I'm trying to understand the proof of the time hierarchy theorem appearing in sipser's book. The proof requires a TM M to simulate an arbitrary TM N without too much slowdown. In particular it is assumed that the encoding of N's tape alphabet using M's alphabet causes only a constant factor slowdown. This seems plausible since if N's alphabet is size k then M can use (log k) cells to represent each symbol that N writes to the tape. But my question is this: If this is how the simulation works then before the simulation starts M will have to change the input so that each bit is repeated (log k) times and I don't know how to do this without adding a quadratic term to the time. I should say its assumed that N's computation is no faster than O(nlog(n)).

1 Answers 1