# Speedup with multi-head Turing Machine

What sort of speedup can a Turing machine with more than one head give vs a one-headed machine (I do not mean multiple tapes, I mean multiple heads operating on the same tape making concurrent edits on different parts of the tape)?

ie. what is the overhead, worst-case, for a one-head Turing Machine to simulate a multi-head Turing Machine as the number of heads grow?

^ This paper ^ says linear time. But the multi-head machines have the additional property of a one-move shift operation (shift a given head to the position of some other given head), is this standard?

Thanks!

• Think about palindrome recognition example: with multiple heads you can do this in linear time, while for one head it requires quadratic time (check references of paper "Palindrome recognition using a multidimensional tape") – user114966 Jul 28 '20 at 22:13

1. k-Band-Simulation von k-Kopf-Turing-Maschinen (1970) - establishes that $$k$$-head and $$k$$-tape can simulate each other without changing computation time.
2. Zwei-Band Simulation von Turingmaschinen (1971) - simulates a machine with $$k$$ heads on an $$m$$-dimensional tape by a machine with 1 normal tape plus 1 stack, establishing a rather precise time bound.
3. Linear-Time Simulation of Multihead Turing Machines (1989) - linearly simulates a machine with $$k$$-heads on a $$d$$-dimensional tape by a machine with $$k$$ separate $$d$$-dimensional tapes plus 1 normal tape.