16
$\begingroup$

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))$?

Improve this question
$\endgroup$
4
  • $\begingroup$ Should the number of tapes be the same, or bounded somehow? $\endgroup$
    – Raphael ♦
    Jul 23, 2012 at 15:53
  • $\begingroup$ And multiple tapes can be simulated in quadratic time on one tape, so if this kind of simulation is fair, why do you expect a difference? Or is linear simulation time fair for other reasons? $\endgroup$
    – Raphael ♦
    Jul 23, 2012 at 15:58
  • $\begingroup$ "I am asking if the simulation can be done with linear overhead" -- I can't match that with the question. Did you mean $o(f(n))$? $\endgroup$
    – Raphael ♦
    Jul 23, 2012 at 18:20
  • 1
    $\begingroup$ @Raphael, I rechecked it and updated the question. The $\omega$ is correct, note that $g$ is an arbitrary function in $\omega(f(n))$. (in the theorem we need something growing faster than $f(n) \lg f(n)$ because the alphabet and the number of states of the simulated machine are not fixed, so there is a constant depending on the machine. $\omega$ is used because of them.) $\endgroup$
    – Kaveh
    Jul 23, 2012 at 18:47

1 Answer 1

Reset to default
7
$\begingroup$

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.
Improve this answer
$\endgroup$
2
  • $\begingroup$ Still there are a few things that are still not completely clear for me, particularly about 8.3 and single-tape simulation of single-tape machines, I will update the answer if needed. $\endgroup$
    – Kaveh
    Aug 16, 2012 at 13:30
  • $\begingroup$ Harmanis'68, Thm. 7 uses the simulation but it is only for $n^2 \leq t(n)$. For smaller $t(n)$ Harmanis gives a direct proof for the time hierarchy theorem. $\endgroup$
    – Kaveh
    Aug 16, 2012 at 21:22

Your Answer

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

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