next up previous contents
Next: Multidimensional TMs, Non-deterministic TMs, Up: Ben's presentation Previous: Two-way infinite tape

Multiple tape TM

Multiple heads, multiple tapes, one control logic. A similar interleaving argument can be used to multiplex these tracks on a single track if the heads are tied together. If they are not tied together, then shifting can be used to move information around to avoid head collisions.
 head one region & & h...
 ...yyyyyyyy & $\ldots$\space &
 zzzzzzzzzzzzzzz \\  \end{tabular}}\end{displaymath} (6)