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

1

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.

  • 0
    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 TM2011-08-14
  • 0
    Oh, so you mean actually converting the input to the multi symbol alphabet?2011-08-14
  • 0
    yeah thats right2011-08-14
  • 0
    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.2011-08-14
  • 0
    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 problem2011-08-14
  • 0
    I do not have Sipser's book close so I cannot have a peak. But how about the algorithm I proposed? I made a little error though, it should move to tape cell $(n-1)\log(|\Gamma|)$2011-08-14
  • 0
    yeah that might work but it seems like it has to remember all the stuff that its writing over right? It cant store it in its register because the amount it will have to store depends on the size of the input. So it seems like it has to zig-zag in order to recall the original input and I couldnt see how to do this in less than quadratic time2011-08-14
  • 0
    Oh sorry youre copying from right to left so youre not writing over anything. But itll still have to zig-zag right? So for each bit of the n bit input it has to move about n cells to the right2011-08-14
  • 0
    Yes indeed just to pick up the values to compute with. By the way, in the same chapter they show that universal simulation only takes O(n log n) overhead, maybe there is a trick you can use from that proof. I never looked into it before so I don't know whether it will be of any use.2011-08-14
  • 0
    ok ill check that out. Thanks for your help2011-08-14
  • 0
    No problem, I still think however that finding the explicit conversion is not necessary, hence both Turing machines in essence do not recognize the same language. However, hence you can describe such a Turing machine with a Turing machine which uses an encoding, you can also think of an equivalent encoded language. In essence you are computing the same problem, it is just represented slightly different.2011-08-14
  • 0
    addition to my last comment: you can see why this is no issue when you look at computational problems involving graphs, no one ever specifies how the graphs are encoded as strings, they just assume that the graph is properly encoded as a string.2011-08-14