0
$\begingroup$

What are the best known upper and lower bounds for simulating t steps of certain models of deterministic turing machines (1 tape, 1 tape with read only input tape, 2 tape, multi tape, with/without random access to memory)?

Edit: I am mainly interested in efficient simulations with the same or with weaker models. Simulations with stronger models are quite efficient in most of the cases.

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ You should also specify the machines on which they are going to be simulated. I think the first chapter in the handbook of theoretical computer science should answer your question. They discuss the simulation of various machine types with various other machine types in that chapter. Although that book is a bit old I don't think much has changed since then. $\endgroup$
    – Kaveh
    Commented Jan 6, 2014 at 3:54
  • $\begingroup$ Does anybody know if the smallest slowdown for a single tape universal turing machine is still logarithmic (or double logarithmic in case a separate read-only input tape is available)? Are there any lower bounds for the computational time of such universal machines known? $\endgroup$
    – Dennis Weyland
    Commented Jan 7, 2014 at 6:08

1 Answer 1

Reset to default
1
$\begingroup$

For what regards (apparently) "weaker" models, one of the recent new results that I saw is that a deterministic Turing machine can be efficiently simulated by a 2-tag system: Damien Woods and Turlough Neary, On the time complexity of 2-tag systems and small universal Turing machines (FOCS 2006)

...

Theorem 1: Given a single tape deterministic Turing machine $M$ that computes in time $t$ then there is a 2-tag system TM that simulates the computation of $M$ and computes in polynomial time $O(t^4(\log t)^2)$.

...

Corollary 1: The small UTMs of Minsky, Rogozhin and others are polynomial time, $O(t^8(\log t)^4)$, simulators of Turing machines.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you very much for your answer. As written in my other comment, I am in particular looking for single tape universal turing machines (with or without a separate read-only input tape). Do you know the current best upper/lower bounds for the time complexity of such machines? $\endgroup$
    – Dennis Weyland
    Commented Jan 7, 2014 at 6:14

Your Answer

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

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