Màquina de Turing alternant

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.

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 $M=(Q,\Gamma ,\delta ,q_{0},g)$on

• $Q$és el conjunt finit d'estats
• $\Gamma$és l'alfabet finit de la cinta
• $\delta :Q\times \Gamma \rightarrow {\mathcal {P}}(Q\times \Gamma \times \{L,R\})$és la funció de transició (L mou el capçal cap a l'esquerra, R cap a la dreta)
• $q_{0}\in Q$és l'estat inicial
• $g:Q\rightarrow \{\wedge ,\vee ,accepta,rebutja\}$especifica el tipus de cada estat

Si M és a l'estat $q\in Q$amb $g(q)=accepta$llavors la configuració es diu que accepta, i si $g(q)=rebutja$la configuració es diu que rebutja. Una configuració amb $g(q)=\wedge$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 $q_{0}$. 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 $t(n)$si, per qualsevol entrada de longitud n, si les configuracions necessiten com a molt $t(n)$passes per marcar la configuració inicial com acceptant o rebutjant. Un ATM decideix un llenguatge en espai $s(n)$si les configuracions necessiten escriure menys de $s(n)$cel·les de la cinta per marcar la configuració inicial com acceptant o rebutjant.

Un llenguatge que es decidible per una ATM en temps $c\cdot t(n)$per alguna constant $c>0$és dins la classe ATIME($t(n)$), i un llenguatge decidible per una ATM en espai $c\cdot s(n)$està dins de SPACE($s(n)$).