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

Improve this question
$\endgroup$
8
  • $\begingroup$ 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? $\endgroup$
    – Kaveh
    Commented Aug 6, 2012 at 3:58
  • $\begingroup$ 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. $\endgroup$
    – Nick
    Commented Aug 6, 2012 at 4:28
  • $\begingroup$ You may want to have a look at these questions: Universal simulation of Turing machines, Alphabet of single-tape Turing machine. $\endgroup$
    – Kaveh
    Commented Aug 6, 2012 at 5:57
  • $\begingroup$ Can you give the page where Sipser says he is allowing alphabets of larger size for simulate TMs? $\endgroup$
    – Kaveh
    Commented Aug 6, 2012 at 6:01
  • 1
    $\begingroup$ 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$. $\endgroup$
    – Kaveh
    Commented Aug 6, 2012 at 11:57

1 Answer 1

Reset to default
2
$\begingroup$

This has been clarified in the book's online errata:

Page 369, Proof of the Time Hierarchy Theorem 9.10.

The proof requires some additional technical discussion at one place. In Stage 4 of D, it simulates M on w. This simulation may require representing each cell of M's tape with several cells on D's tape because M's tape alphabet is arbitrary and D's tape alphabet is fixed. However, initializating the simulation by converting D's input w to this representation involves rewriting w so that its symbols are spread apart by several cells. If we use the obvious copying procedure for spreading w, this conversion would involve O(n^2) time and that would exceed the O(t(n)) time bound for small t. Instead, we observe that D operates on inputs w of the form x10^k where x = ‹M›, and we only need to carry out the simulation when k is large. We consider only k > |x|^2. We can spread w by first using the obvious copying procedure for x and then counting trailing 0s and rewriting these by using that count. The time for spreading x is O(|x|^2) which is O(n). The time for counting the 0s is O(n log n) which is O(t(n)) because t is time constructible.

Reported 11/15/12 by Kaveh Ghasemloo of the University of Toronto.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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