Flexoelectricity

Template:Turing 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.

Formal definition

A multitape Turing machine can be formally defined as a 6-tuple $M=⟨Q,\mathrm{\Sigma },\mathrm{\Gamma },\delta ,q_0,F⟩$, where

• $Q$ is a finite set of states
• $\mathrm{\Sigma }$ is a finite set of symbols called the tape alphabet
• $\mathrm{\Gamma }\in Q$
• $q_0\in Q$ is the initial state
• $F\subseteq Q$ is the set of final or accepting states.
• $\delta \subseteq (Q\mathrm{\setminus }A\times \mathrm{\Sigma })\times (Q\times \mathrm{\Sigma }\times d)$ is a relation on states and symbols called the transition relation.
• $\delta (Q_i,[x_1,x_2...x_n])=(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= $⟨Q,\mathrm{\Sigma },\mathrm{\Gamma },\delta ,q_0,F⟩$ 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^{\prime }$

If all but the first track is ignored then M and M' are clearly equivalent.

• $M^{\prime }\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= $⟨Q,\mathrm{\Sigma }\times B,\mathrm{\Gamma }\times \mathrm{\Gamma },{\delta }^{\prime },q_0,F⟩$ with the transition function $\delta (q_i,[x_1,x_2])={\delta }^{\prime }(q_i,[x_1,x_2])$

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