Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question

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

This clearly solves the problem you are having, as now you can assume that they have the same alphabet without loosing generality.

share|cite|improve this answer
Thanks for your help Dimitri. I think I have the same confusion regarding the proposition in AB because they are using the same simulation. Its clear that each simulated step costs a constant number of real steps so thats fine. But I still dont know how to set up the simulation (ie change each input bit to its (log k)-bit representation) in less than quadratic time. It seems like AB might be allowing the simulation to be run on a multitape TM. In this case the set-up can clearly be done in linear time. In sipser's case the simulation is performed on a single,unidirectional tape TM – Nick Aug 14 '11 at 19:48
Oh, so you mean actually converting the input to the multi symbol alphabet? – sxd Aug 14 '11 at 19:52
yeah thats right – Nick Aug 14 '11 at 20:00
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
In response to your deleted post: Well in sipser's book both machines share the input alphabet. It seems important to the diagonalization argument in the time hierarchy theorem that the simulation be run on the input itself and not a coded form of the input. but maybe its not in which case your comment would solve the problem – Nick Aug 14 '11 at 20:34

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.