# For the time hierarchy theorem, how is the input translated efficiently?

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(n\log(n))$.

• Note that the simulations are not done on a single tape machine, and with multiple tapes you can write it in linear-time. Does this answer your question? – Kaveh Aug 6 '12 at 3:58
• Thanks, Kaveh! In the 2006 edition that I have the machine has only one tape although, in the proof, its alphabet is taken to be large enough to simulate multiple tracks with its single tape. Thanks and I hope I haven't misunderstood your comment. – Nick Aug 6 '12 at 4:28
• You may want to have a look at these questions: Universal simulation of Turing machines, Alphabet of single-tape Turing machine. – Kaveh Aug 6 '12 at 5:57
• Can you give the page where Sipser says he is allowing alphabets of larger size for simulate TMs? – Kaveh Aug 6 '12 at 6:01
• Yes, I checked the theorem and didn't see he mentioning that, I just wanted to make sure I am not missing it. Sipser is a very well-written book. As you can see from my question I am also a little bit confused about the simulation theorems. :) The original paper uses multiple tapes and similarly do some other books that I have checked, e.g. Arora and Barak. Based on Emanuele Viola's question remaining open I think it is unlikely that the theorem holds for larger tape alphabets when time is less that $n^2$. – Kaveh Aug 6 '12 at 11:57