<p>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:
<a href="http://arxiv.org/abs/cs/0612089" rel="nofollow">Damien Woods and Turlough Neary, On the time complexity of 2-tag systems and
small universal Turing machines (FOCS 2006)</a></p>

<p>...</p>

<p><strong>Theorem 1:</strong> 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)$.</p>

<p>...</p>

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

CC BY-SA 3.0
2014-01-07T06:14:22.470Z
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?
Dennis Weyland
CC BY-SA 3.0
2014-01-06T09:52:48.313Z
2014-01-06T09:59:59.273Z
2014-01-06T09:59:59.273Z
Marzio De Biasi
<p>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)?</p>

<p>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.</p>

CC BY-SA 3.0
2014-01-06T03:54:40.820Z
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.
Kaveh
CC BY-SA 3.0
2014-01-07T06:08:21.680Z
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?
Dennis Weyland
<computability><turing-machines>
Simulation of deterministic turing machines
Dennis Weyland
# Simulation of deterministic turing machines

(Asked by: username_0 on 2014-01-06)

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.

**Tags:** computability, turing-machines
> **Comments:**
> **username_1**: 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.  
> **username_0**: 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?  

---

## 1 answers

### Answer by username_2 on 2014-01-06. Score: 1

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)](http://arxiv.org/abs/cs/0612089)

...

**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.

> **Comments:**
> **username_0**: 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?  

---

