Màquina de Turing alternant
Aquest article (o aquesta secció) necessita alguna millora en els seus enllaços interns. Falta enllaçar les paraules més significatives als articles corresponents |
En teoria de la computació, una Màquina de Turing alternant (ATM) és una màquina de Turing no determinista amb una regla per acceptar computacions que generalitzen les regles usades en la definició de les classes de complexitat NP i co-NP.[1][2][1]
Definició
Descripció informal
La definició de la classe NP usa el mode de computació existencial: si qualsevol elecció porta cap un estat que accepta, llavors tota la computació s'accepta. La definició de co-NP usa el mode universal per la computació: només si totes les eleccions porten cap a un estat que accepta, llavors la computació s'accepta. Una màquina de Turing alternant va alternant entre els dos modes.
Una màquina de Turing alternant és una màquina de Turing no determinista els estats de la qual està dividida en dos conjunts: estats existencials i estats universals. Un estat existencial accepta si alguna transició porta cap a un esta que accepta. Un estat universal accepta si totes les transicions porten a un estat que accepta. La màquina com un tot accepta si l'estat inicial accepta.
Definició formal
Formalment, una màquina de Turing alternant és una 5-tupla on
- és el conjunt finit d'estats
- és l'alfabet finit de la cinta
- és la funció de transició (L mou el capçal cap a l'esquerra, R cap a la dreta)
- és l'estat inicial
- especifica el tipus de cada estat
Si M és a l'estat amb llavors la configuració es diu que accepta, i si la configuració es diu que rebutja. Una configuració amb es diu que accepta si totes les configuracions que es pot arribar en un pas accepten, o rebutja si alguna de les configuracions rebutja. M es diu que accepta la cadena d'entrada w si la configuració inicial de M (l'estat de M és . el capçal és al final de la cinta i la cinta conté w) accepta i que rebutja si la configuració inicial rebutja.
Límit de recursos
Una ATM decideix un llenguatge formal en temps si, per qualsevol entrada de longitud n, si les configuracions necessiten com a molt passes per marcar la configuració inicial com acceptant o rebutjant. Un ATM decideix un llenguatge en espai si les configuracions necessiten escriure menys de cel·les de la cinta per marcar la configuració inicial com acceptant o rebutjant.
Un llenguatge que es decidible per una ATM en temps per alguna constant és dins la classe ATIME(), i un llenguatge decidible per una ATM en espai està dins de SPACE().
Referències
- ↑ 1,0 1,1 Chandra, Ashok K.; Kozen, Dexter C.; Stockmeyer, Larry J. «Alternation». J. ACM, 28, 1, 1981-1, pàg. 114–133. DOI: 10.1145/322234.322243. ISSN: 0004-5411.
- ↑ Chandra, A. K.; Stockmeyer, L. J. «Alternation». Proc. 17th IEEE Symp. on Foundations of Computer Science., 1976-10, pàg. 98–108. DOI: 10.1109/SFCS.1976.4.