<p>If we have a fixed number of tapes then yes we can simulate them without the logarithmic overhead. E.g simulation of two-tape (and in general $k$-tape) TMs on a two-tape machine can be done without the logarithmic factor increase.</p>

<p>If we want to simulate an arbitrary constant number of tapes then AFAIK we don't know any such simulation. </p>

<p>See these questions and the references there:</p>

<p><a href="https://cstheory.stackexchange.com/q/5297/">Justification of log f in DTIME hierarchy theorem</a></p>

<p><a href="https://cs.stackexchange.com/q/2878/">Universal simulation of Turing machines</a></p>

CC BY-SA 3.0
2016-03-01T02:33:03.057Z
Hmm interesting. What about a single tape with fixed input alphabet (ie the input output colors are restricted to $\{0,1,\#\}$ (blank space) and  still multil head?
Cpt Wobbles 
CC BY-SA 3.0
2016-03-01T08:55:03.120Z
A single tape with multiple heads is the same as multiple tapes, up to linear factors.
Emil Jeřábek
CC BY-SA 3.0
2016-03-01T14:22:31.957Z
A nice place to look for information about different versions of TMs is the first chapter of handbook of theoretical computer science.
Kaveh
CC BY-SA 4.0
2022-03-17T12:58:15.313Z
Would you have a reference for constant overhead simulation of k tapes by 2 tapes ? I've yet to find it in the links you posted.
ULechine
CC BY-SA 3.0
2016-02-29T15:24:21.887Z
2016-02-29T15:37:30.587Z
2017-04-13T12:48:30.830Z
Kaveh
<p>It is common knowledge that a universal Turing machine can simulate any Turing machine with logarithmic overhead. Is it possible to make this overhead constant by constructing an analogous "Universal" multi head Turing machine?</p>

CC BY-SA 3.0
2016-02-29T14:48:15.050Z
I believe that there are machine models where the time-complexity overhead factor is a constant.  Maybe someone out there can provide some examples.  :)
Michael Wehar
<turing-machines><universal-turing-machines>
Multi Head universal Turing machine
Cpt Wobbles 
# Multi Head universal Turing machine

(Asked by: username_0 on 2016-02-29)

It is common knowledge that a universal Turing machine can simulate any Turing machine with logarithmic overhead. Is it possible to make this overhead constant by constructing an analogous "Universal" multi head Turing machine?

**Tags:** turing-machines, universal-turing-machines
> **Comments:**
> **username_1**: I believe that there are machine models where the time-complexity overhead factor is a constant.  Maybe someone out there can provide some examples.  :)  

---

## 1 answers

### Answer by username_2 on 2016-02-29. Score: 3 | Accepted answer

If we have a fixed number of tapes then yes we can simulate them without the logarithmic overhead. E.g simulation of two-tape (and in general $k$-tape) TMs on a two-tape machine can be done without the logarithmic factor increase.

If we want to simulate an arbitrary constant number of tapes then AFAIK we don't know any such simulation.

See these questions and the references there:

[Justification of log f in DTIME hierarchy theorem](https://cstheory.stackexchange.com/q/5297/)

[Universal simulation of Turing machines](https://cs.stackexchange.com/q/2878/)

> **Comments:**
> **username_0**: Hmm interesting. What about a single tape with fixed input alphabet (ie the input output colors are restricted to $\{0,1,\#\}$ (blank space) and  still multil head?  
> **username_3**: A single tape with multiple heads is the same as multiple tapes, up to linear factors.  
> **username_2**: A nice place to look for information about different versions of TMs is the first chapter of handbook of theoretical computer science.  
> **username_4**: Would you have a reference for constant overhead simulation of k tapes by 2 tapes ? I've yet to find it in the links you posted.  

---

