Multi-track Turing machine

A Multitrack Turing machine is a specific type of multi-tape Turing machine.

In a standard n-tape Turing machine, n heads move independently along n tracks. In a n-track Turing machine, one head reads and writes on all tracks simultaneously. A tape position in an n-track Turing Machine contains n symbols from the tape alphabet. It is equivalent to the standard Turing machine and therefore accepts precisely the recursively enumerable languages.

Formal definition

edit

A multitrack Turing machine with  -tapes can be formally defined as a 6-tuple , where

  •   is a finite set of states;
  •   is a finite set of input symbols, that is, the set of symbols allowed to appear in the initial tape contents;
  •   is a finite set of tape alphabet symbols;
  •   is the initial state;
  •   is the set of final or accepting states;
  •   is a partial function called the transition function.
Sometimes also denoted as  , where  .

A non-deterministic variant can be defined by replacing the transition function   by a transition relation  .

Proof of equivalency to standard Turing machine

edit

This will prove that a two-track Turing machine is equivalent to a standard Turing machine. This can be generalized to a n-track Turing machine. Let L be a recursively enumerable language. Let   be standard Turing machine that accepts L. Let M' is a two-track Turing machine. To prove   it must be shown that   and  .

  •  

If the second track is ignored then M and M' are clearly equivalent.

  •  

The tape alphabet of a one-track Turing machine equivalent to a two-track Turing machine consists of an ordered pair. The input symbol a of a Turing machine M' can be identified as an ordered pair   of Turing machine M. The one-track Turing machine is:

  with the transition function  

This machine also accepts L.

References

edit
  • Thomas A. Sudkamp (2006). Languages and Machines, Third edition. Addison-Wesley. ISBN 0-321-32221-5. Chapter 8.6: Multitape Machines: pp 269–271