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?


  • 2
    $\begingroup$ 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") $\endgroup$ – Dmitry Jul 28 '20 at 22:13

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy