Multi-track Turing machine
||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.
Thomas A. Sudkamp (2006). Languages and Machines, Third edition. Addison-Wesley. ISBN 0-321-32221-5. Chapter 8.6: Multitape Machines: pp 269–271