Màquina de Turing alternante

Plantilla:Teoria d'autómates En la teoria de la complexitat computacional, una màquina de Turing alternante (ATM) és una màquina de Turing no determinista (NTM) en una regla per a l'acceptació de còmput que generalisa les regles usades en la definició de les classes de complexitat NP i co-NP. El concepte d'una ATM va ser establit per Chandra i Stockmeyer en 1976 (vore referències).

Descripció informal

La definició de NP usa el modo existencial de computació: Si qualsevol elecció du a un estat d'acceptació, llavors la computació completa accepta. La definició de co-NP usa el modo universal de computació: solament si totes les opcions duen a un estat d'acceptació, la computació completa accepta. Una màquina de Turing alternante (o per a ser més precisos, la definició de l'acceptació de tal màquina) alterna entre estos modos.

Una màquina de Turing alternante és una màquina de Turing no determinista els estats de la qual es dividixen en dos grups: estats existencials i estats universals. Un estat existencial està acceptant si alguna transició conduïx a un estat d'acceptació; un estat universal està acceptant si cada transició conduïx a un estat d'acceptació. (Per lo tant un estat universal en transicions accepta incondicionalment, un estat existencial sense transicions rebuja incondicionalment). La màquina com un conjunt accepta si l'estat inicial està acceptant.

Definició formal

Formalment, una màquina de Turing alternante (d'una cinta) és una 5 tupla $M=(Q,\Gamma ,\delta ,q_0,g)$ a on

• $Q$ és el conjunt finit d'estats
• $\Gamma$ és l'alfabet finit de la cinta
• $\delta :Q\times \Gamma \to 𝒫(Q\times \Gamma \times \{L,R\})$ és cridada la funció de transició (L desplaça el cap a l'esquerra i R desplaça el cap a la dreta)
• $q_0\in Q$ és l'estat inicial
• $g:Q\to \{\wedge ,\vee ,acepta,rechaza\}$ especifica el tipo de cada estat

Si M és un estat $q\in Q$ en $g(q)=acepta$ llavors eixa configuració es diu que és aceptante, i si $g(q)=rechaza$ la configuració es diu que és rechazante. Una configuració en $g(q)=\wedge$ es diu que és aceptante si totes les configuracions en un sol pas són aceptantes, i rechazante si alguna configuració accessible en un sol pas és rechazante. Una configuració en $g(q)=\vee$ es diu que és aceptante quan existix alguna configuració accessible en un sol pas que és aceptante i recrechazante quan totes les configuracions en un sol pas són rechazantes (est és el tipo de tots els estats en una NTM). Es diu que M accepta una cadena d'entrada w si la configuració inicial de M és aceptante (l'estat de M és $q_0$, el cap està en l'extrem esquerre de la cinta i la cinta conté w), i rebuja si la configuració inicial és rechazante.

Vore també

• Màquina de Turing
• Màquina de Turing universal
• Alan Turing

Bibliografia

• Chandra, A.K., i Stockmeyer, L.J, 'Alternation', Proc. 17ª IEEE Symp. Sobre Foundations of Computer Science, Houston, Texas, 1976, pp. 98-108.
• Chandra, A.K. I Kozen, D.C. i Stockmeyer, L.J., 'Alternation', Journal of the ACM, Vol. 28, N.º 1, pp. 114-133, 1981.
• Michael Sipser (1997). Introducció a la teoria de la computació, Publicació PWS. ISBN 0-534-94728-X. Secció 10.3: Alternança, pp. 348-354.
• Michael Sipser (2006). Introducció a la Teoria de la Computació, 2.ª edició, Publicació PWS. ISBN 0-534-95097-3. Secció 10.3: Alternança, pp. 380-386.

• Christos Papadimitriou (1993). Complex computacional, 1.ª edició, Addison Wesley. ISBN 0-201-53082-1. Secció 16.2: Alternança, pp. 399-401.