- the description of a TM $langle M rangle$, and
- an input string $x$,
runs for $g(|x|)$ steps and returns $M$’s answer on $x$. And $g$ can be taken to be any function in $omega(f(n)lg f(n))$. My questions are:
- What is the best known simulation result on a single tape TM? Does the result above also still hold?
- 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))$?
Asked By : Kaveh
Answered By : Kaveh
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). References:
- 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
(page 84) - 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:
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/2878