Loading AI tools
From Wikipedia, the free encyclopedia
A Multitrack Turing machine is a specific type of multi-tape Turing machine.
This article may be too technical for most readers to understand. (June 2018) |
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 -tapes can be formally defined as a 6-tuple, where
A non-deterministic variant can be defined by replacing the transition function by a transition relation .
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:
This machine also accepts L.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.