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.[1]
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.[2] 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.[3]
Definició formal
modificaA 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
modificaS'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
modifica- ↑ Michael., Sipser,. Introduction to the theory of computation. 2a edició. Boston: Thomson Course Technology, 2006. ISBN 0534950973.
- ↑ H., Papadimitriou, Christos. Computational complexity. Reading, Mass.: Addison-Wesley, 1994. ISBN 0201530821.
- ↑ C., Martin, John. Introduction to languages and the theory of computation. 4th ed. Nova York, NY: McGraw-Hill, 2011. ISBN 9780073191461.