patternMinor
Universal simulation of Turing machines
Viewed 0 times
turinguniversalmachinessimulation
Problem
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
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))$?
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:
-
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))$?
Solution
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:
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:
- 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.
Context
StackExchange Computer Science Q#2878, answer score: 7
Revisions (0)
No revisions yet.