Màquina de Turing multicinta

Una màquina de Turing multipista és una màquina de Turing que té múltiples cintes. Cada cinta té el seu propi capçal per llegir o escriure. Inicialment l'entrada apareix a la cinta número 1 i la resta comencen buides.

Tot i aquest model sembla molt més potent que una màquina de Turing tradicional amb una sola cinta, qualsevol màquina amb una sola cinta pot simular una màquina multi-cinta (sense importar el nombre de cintes) utilitzant només un temps quadràtic respecte al temps original. Per tant, una màquina multicinta no pot calcular cap altre funció que no pugui calcular una màquina amb una sola cinta i cap de les classes de complexitat es veuen afectades per l'increment en el nombre de cintes de la màquina.

Definició formal

A màquina de Turnig amb k-cintes es pot descriure com una 6-tupla $M=\langle Q,\Gamma ,s,b,F,\delta \rangle$ on:

• $Q$ és un conjunt finit d'estats
• $\Gamma$ és un conjunt finit de l'alfabet de cinta
• $s\in Q$ és l'estat inicial
• $b\in \Gamma$ és el símbol blanc
• $F\subseteq Q$ és el conjunt d'estats que accepten
• $\delta :Q\times \Gamma ^{k}\rightarrow Q\times (\Gamma \times \{L,R,S\})^{k}$ és una funció parcial, anomenada funció de transferència, on k és el nombre de cintes, L és el moviment a l'esquerra, R el moviment a la dreta i S és no moure el capçal

Màquina de Turing de doble pila

S'anomena màquina de Turing de doble pila a la màquina de Turing que té una cinta d'entrada només de lectura i dos cintes per emmagatzemament de símbols.