- Multi-track Turing machine
-
Turing machine(s) Machina - Universal Turing machine
- Alternating Turing machine
- Quantum Turing machine
- Read-only Turing machine
- Read-only right moving Turing Machines
- Probabilistic Turing machine
- Multi-track Turing machine
- Turing machine equivalents
- Turing machine examples
- Wolfram's 2-state 3-symbol..
Science This box: view · 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. Formal definition
A multitape Turing machine can be formally defined as a 6-tuple , where
- Q 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 relation on states and symbols called the transition relation.
where
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 than 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.
References
Thomas A. Sudkamp (2006). Languages and Machines, Third edition. Adison Wesley. ISBN 0-321-32221-5. Chapter 8.6: Multitape Machines: pp 269-271
Categories:
Wikimedia Foundation. 2010.
Look at other dictionaries:
Turing machine equivalents — Turing machine(s) Machina Universal Turing machine Alternating Turing machine Quantum Turing machine Read only Turing machine Read only right moving Turing Machines Probabilistic Turing machine Multi track Turing machine Turing machine… … Wikipedia
Turing machine — For the test of artificial intelligence, see Turing test. For the instrumental rock band, see Turing Machine (band). Turing machine(s) Machina Universal Turing machine Alternating Turing machine Quantum Turing machine Read only Turing machine… … Wikipedia
Non-deterministic Turing machine — Turing machine(s) Machina Universal Turing machine Alternating Turing machine Quantum Turing machine Read only Turing machine Read only right moving Turing Machines Probabilistic Turing machine Multi track Turing machine Turing machine… … Wikipedia
Probabilistic Turing machine — Turing machine(s) Machina Universal Turing machine Alternating Turing machine Quantum Turing machine Read only Turing machine Read only right moving Turing Machines Probabilistic Turing machine Multi track Turing machine Turing machine… … Wikipedia
Квантовая машина Тьюринга — Машина Тьюринга Варианты машин Универсальная машина Тьюринга Квантовая машина Тьюринга en:Read only Turing machine en:Read only right moving Turing Machines Вероятностная машина Тьюринга Неде … Википедия
Недетерминированная машина Тьюринга — Машина Тьюринга Варианты машин Универсальная машина Тьюринга Квантовая машина Тьюринга en:Read only Turing machine en:Read only right moving Turing Machines Вероятностная машина Тьюринга Недетер … Википедия
Вероятностная машина Тьюринга — Машина Тьюринга Варианты машин Универсальная машина Тьюринга Квантовая машина Тьюринга en:Read only Turing machine en:Read only right moving Turing Machines Вероятностная машина Тьюринга Не … Википедия
History of computing hardware — Computing hardware is a platform for information processing (block diagram) The history of computing hardware is the record of the ongoing effort to make computer hardware faster, cheaper, and capable of storing more data. Computing hardware… … Wikipedia
Conway's Game of Life — Conway game , which redirects to here, can also refer to games as defined by surreal numbers, which John Conway also developed … Wikipedia
Computer — For other uses, see Computer (disambiguation). Computer technology redirects here. For the company, see Computer Technology Limited. Computer … Wikipedia
18+© Academic, 2000-2024- Contact us: Technical Support, Advertising
Dictionaries export, created on PHP, Joomla, Drupal, WordPress, MODx.Share the article and excerpts
Multi-track Turing machine
- Multi-track Turing machine
-
Turing machine(s) Machina - Universal Turing machine
- Alternating Turing machine
- Quantum Turing machine
- Read-only Turing machine
- Read-only right moving Turing Machines
- Probabilistic Turing machine
- Multi-track Turing machine
- Turing machine equivalents
- Turing machine examples
- Wolfram's 2-state 3-symbol..
Science