# Simulation of deterministic turing machines

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.

• 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. Jan 6, 2014 at 3:54
• 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? Jan 7, 2014 at 6:08

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.