Multi-track Turing machine
This article may be too technical for most readers to understand. Please help improve it to make it understandable to non-experts, without removing the technical details. (June 2018) (Learn how and when to remove this template message)
This article needs more links to other articles to help integrate it into the encyclopedia. (September 2016) (Learn how and when to remove this template message)
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 a 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 -tapes can be formally defined as a 6-tuple , where
- is a finite set of states
- is a finite set of symbols called the tape alphabet
- 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
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 M= be standard Turing machine that accepts L. Let M' is a two-track Turing machine. To prove M=M' it must be shown that M M' and M' M
If all but the first 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 [x,y] of Turing machine M. The one-track Turing machine is:
M= with the transition function
This machine also accepts L.