What is the best known simulation result on a single tape TM? Does the result above also still hold?
We can simulate a multiple-tape TM on a single-tape TM with quadratic increase in time. The simulation time is $O(n^2)$. The quadratic increase is required since there are languages (e.g. palindromes) that require time $\Omega(n^2)$ on a single-tape DTM but can be solved in time $O(n)$ on a two-tape DTM.
In short, the result above does not work when the simulator is a single-tape TM.
For simulation of single-tape TMs on a single-tape TM (with arbitrary finite alphabet), the result holds, i.e. the simulation can be done with $\lg$ factor increase in time. See (2) and (3). The reference seems to be (6).
Is there any improvement on [HS66]? Can we simulate TMs on a two-tape TM for $f(n)$ steps in a faster way? Can we take $g(n)$ to be in $\omega(f(n))$ in place of $\omega(f(n)\lg f(n))$?
It seems that there hasn't been any improvement since that would imply a better time hierarchy theorem than currently known.
Correction: The usual hierarchy theorems are based on time complexity classes defined using single tape TMs. For $n$-tape TMs a tight result similar to the space hierarchy theorem is proven by Furer in 1982 (5). The $\lg$ factor is not needed. Also see (4).
Peter van Emde Boas, "Machine Models and Simulation", in Handbook of Theoretical Computer Science, 1990
(in particular, pp. 18-21)
Michael Sipser, "Introduction to the Theory of Computation", 2006
(time complexity classes are defined using TMs with single-tape infinite in both directions and arbitrary finite alphabet, see pages 140 and 341)
Odifreddi , "Classical Recursion Theory", vol. I & II, 1989 & 1999
(definitions are similar to Sipser, see Def. I.4.1 in vol. I page 48, Def. VII.4.1 in vol. II page 67, and Thm. VII.4.15 in vol. II page 83)
Piergiorgio Odifreddi, "Classical Recursion Theory", vol. II, 1999
Martin Fürer, "The Tight Deterministic Time Hierarchy", 1982
Juris Hartmanis, "Computational Complexity of One-Tape Turing Machine Computations", 1968
F.C. Hennie and R.E. Stearns, "Two-Tape Simulation of Multitape Turing Machines", 1966
Other related questions:
- Lower bounds and class separation,
- Justification of $\lg f$ in DTIME hierarchy theorem,
- Alphabet of single-tape Turing machine,
- For the time hierarchy theorem, how is the input translated efficiently?,
- a comment by Luca Trevisan.