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
-
$\begingroup$ The same question was also asked here: cstheory.stackexchange.com/questions/4928/… $\endgroup$– ManuCommented Jan 5 at 21:36
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
12
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 clearly solves the problem you are having, as now you can assume that they have the same alphabet without loosing generality.
-
$\begingroup$ 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 $\endgroup$– NickCommented Aug 14, 2011 at 19:48
-
$\begingroup$ Oh, so you mean actually converting the input to the multi symbol alphabet? $\endgroup$– sxdCommented Aug 14, 2011 at 19:52
-
-
$\begingroup$ 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. $\endgroup$– sxdCommented Aug 14, 2011 at 20:30
-
$\begingroup$ 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 $\endgroup$– NickCommented Aug 14, 2011 at 20:34