[Solved]: Universal simulation of Turing machines

Problem Detail: 

Let $f$ be a fixed time-constructable function.

The classical universal simulation result for TMs (Hennie and Stearns, 1966) states that there is a two-tape TM $U$ such that given

• 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:

1. What is the best known simulation result on a single tape TM? Does the result above also still hold?

2. 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:

1. Peter van Emde Boas, "Machine Models and Simulation", in Handbook of Theoretical Computer Science, 1990
   (in particular, pp. 18-21)

2. 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)

3. 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)

4. Piergiorgio Odifreddi, "Classical Recursion Theory", vol. II, 1999
   (page 84)

5. Martin Fürer, "The Tight Deterministic Time Hierarchy", 1982

6. Juris Hartmanis, "Computational Complexity of One-Tape Turing Machine Computations", 1968

7. F.C. Hennie and R.E. Stearns, "Two-Tape Simulation of Multitape Turing Machines", 1966

8. Other related questions:

   1. Lower bounds and class separation,
   2. Justification of $\lg f$ in DTIME hierarchy theorem,
   3. Alphabet of single-tape Turing machine,
   4. For the time hierarchy theorem, how is the input translated efficiently?,
   5. a comment by Luca Trevisan.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/2878