Màquina de Turing multicinta

Una màquina de Turing multicinta, també denominada màquina de Turing de cintes múltiples, és una variant de la màquina de Turing que utilisa vàries cintes. Cada cinta té el seu propi cabezal per a llectura i escritura. Inicialment, l'entrada apareix en la cinta 1, i les demés comencen en blanc.

Este model sembla intuitivamente molt més potent que el model d'una sola cinta, pero qualsevol màquina de cintes múltiples (sense importar quàntes cintes tinga) pot ser simulada per una màquina d'una sola cinta utilisant solament més temps de càlcul, que s'incrementa cuadráticamente. És dir, qualsevol llenguage que puga ser decidit en O(t(n)) temps per una màquina de Turing de cintes múltiples pot ser decidit en O(t²(n)) per una màquina d'una sola cinta.

Per lo tant, les màquines de cintes múltiples no poden calcular més funcions que les màquines d'una sola cinta, i cap de les classes robustes de complexitat (com la de temps polinòmic) es veu afectada per un canvi entre màquines d'una sola cinta i de cintes múltiples.

Definició formal

Una màquina de Turing de $k$ cintes es pot definir formalment com una 7-tupla $M=⟨Q,\Gamma ,b,\Sigma ,\delta ,q_0,F⟩$, seguint la notació d'una màquina de Turing:

• $\Gamma$ és un conjunt finit i no buit de símbols de l'alfabet de la cinta;
• $b\in \Gamma$ és el símbol en blanc (l'únic símbol que pot aparéixer en la cinta infinitament a sovint en qualsevol pas durant el càlcul);
• $\Sigma \subseteq \Gamma \setminus \{b\}$ és el conjunt de símbols d'entrada, és dir, el conjunt de símbols que poden aparéixer en el contingut inicial de la cinta;
• $Q$ és un conjunt finit i no buit de estats;
• $q_0\in Q$ és el estat inicial;
• $F\subseteq Q$ és el conjunt de estats finals o estats d'acceptació. Es diu que el contingut inicial de la cinta és acceptat per $M$ si finalment es deté en un estat de $F$.
• $\delta :(Q\setminus F)\times {\Gamma }^k\to Q\times {\Gamma }^k\times \{L,R{\}}^k$ és una funció parcial cridada funció de transició, a on L representa el desplaçament a l'esquerra i R el desplaçament a la dreta.

Una màquina de Turing de $k$ cintes, $M$, a on $k$ és el número de cintes assignades, realisa els càlculs de la següent manera: $M$ comença en el seu estat inicial $q_0$. Este estat es definix pel fet de que totes les cintes tenen un cabezal que comença en la posició més a l'esquerra, junt en una entrada $w=w_1{w}_2\mathrm{...}{w}_n\in {\Sigma }^{*}$ en les posicions més a l'esquerra de $n$ de la primera cinta. Tots els demés símbols de cada cinta són el símbol en blanc definit per $b$. Un pas de la màquina es realisa evaluant la funció de transició. Açò es conseguix prenent l'estat actual $q_i\in Q$ i el conjunt de símbols alfabètics sobre els que es troben els cabezales, denotat com ${\Gamma }^k$. La funció de transició pren abdós paràmetros i genera els tres elements necessaris per a una transició: el nou estat $q_j\in Q$ al que transita $M$, un nou conjunt de símbols alfabètics ${\Gamma }^k$ que cada u dels cabezales $k$ escriurà en les seues respectives celes, i un conjunt d'instruccions de desplaçament $\{L,R{\}}^k$ que indicaran a cada cabezal en quina direcció moure's (una cela a l'esquerra o a la dreta) despuix d'escriure els nous símbols. La funció de transició itera fins que $M$ alcança un estat final pertanyent al conjunt $F$, moment en el que es deté.

Màquina de Turing de dos piles

Les màquines de Turing de dos piles tenen una entrada de solament llectura i dos cintes d'almagasenament. Si el cabezal es desplaça cap a l'esquerra en qualsevol de les cintes, s'imprimix un espai en blanc en dita cinta, pero es pot imprimir un símbol d'una biblioteca.

Vore també

• Màquina de Turing
• Màquina de Turing universal
• Màquina de Turing alternante
• Màquina de Turing provabilística
• Equivalents de la màquina de Turing