# 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?

https://link.springer.com/content/pdf/10.1007/3-540-08342-1_35.pdf

^ 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") – Dmitry Jul 28 '20 at 22:13

## 1 Answer

First, the one-move shift is definitely NOT standard, but, as far as I understand, it only strengthens the result in that article. If a machine with the special operation can be simulated, then of course a machine without that operation can as well.

Second, here are some papers by Hans-Jörg Stoß dealing with multi-head machines. No one-move shifts here.

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.

Unfortunately, the first two are, as far as I know, only in German. The full text of the third one (translated) is here: doi.org/10.1016/0890-5401(89)90037-0