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 on:
és un conjunt finit d'estats és un conjunt finit de l'alfabet de cinta és l'estat inicial és el símbol blanc és el conjunt d'estats que accepten é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.
Referències
Categoria:Màquines de Turing