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
Alan Turing Category:Turing machine
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 $M= \langle Q, \Sigma, \Gamma, \delta, q_0, F \rangle$, where Q is a finite set of states Σ is a finite set of symbols called the tape alphabet $\Gamma \in Q$ $q_0 \in Q$ is the initial state $F \subseteq Q$ is the set of final or accepting states. $\delta \subseteq \left(Q \backslash A \times \Sigma\right) \times \left( Q \times \Sigma \times d \right)$ is a relation on states and symbols called the transition relation. $\delta \left(Q_i,[x_1,x_2...x_n]\right)=(Q_j,[y_1,y_2...y_n],d)$ where $d \in {L,R}$ 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= $\langle Q, \Sigma, \Gamma, \delta, q_0, F \rangle$ 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 $\subseteq$ M' and M' $\subseteq$ M. $M \subseteq M'$ If all but the first track is ignored than M and M' are clearly equivalent. $M' \subseteq M$ 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= $\langle Q, \Sigma \times {B}, \Gamma \times \Gamma, \delta ', q_0, F \rangle$ with the transition function $\delta \left(q_i,[x_1,x_2]\right)=\delta ' \left(q_i,[x_1,x_2]\right)$ 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 Wikimedia Foundation. 2010. Игры ⚽ Поможем решить контрольную работу Multi-touch gestures Multi-utility 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. Mark and share Search through all dictionaries Translate… Search Internet Share the article and excerpts Direct link … Do a right-click on the link above and select “Copy Link”