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

modifica

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

modifica

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

modifica
  1. Michael., Sipser,. Introduction to the theory of computation. 2a edició. Boston: Thomson Course Technology, 2006. ISBN 0534950973. 
  2. H., Papadimitriou, Christos. Computational complexity. Reading, Mass.: Addison-Wesley, 1994. ISBN 0201530821. 
  3. C., Martin, John. Introduction to languages and the theory of computation. 4th ed. Nova York, NY: McGraw-Hill, 2011. ISBN 9780073191461.