# basic question about simulating Turing machines with larger alphabets

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)).

-

In chapter 1 of Complexity theory a modern approach, they show that for every Turing machine with an arbitrary alphabet, you can find an equivalent Turing machine which only uses a tape alphabet with 4 symbols $\{0,1,\square,\triangleright\}$ with a very small slowdown. See Claim 1.8 in http://www.cs.princeton.edu/theory/complexity/modelchap.pdf
This could be a possible algorithm me thinks If the input has n symbols move to tape cell $\log_2(n-1)$ and insert $\log_2$(value of symbol n) at this position then move to tape cell $\log_2(n-2)$ and insert $\log_2$(value of symbol n-1) ... Sorry for removing my earlier comment but it didn't make much sense. –  sxd Aug 14 '11 at 20:30