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.

  • 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 Jan 6 '14 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 Jan 7 '14 at 6:08

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.

| cite | improve this answer | |
  • $\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 Jan 7 '14 at 6:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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