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.
A multitrack Turing machine with
, where A non-deterministic variant can be defined by replacing the transition function
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.
be standard Turing machine that accepts L. Let M' is a two-track Turing machine.
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: This machine also accepts L.