Máquina de Turing alternante

En la teoría de la complejidad computacional , una máquina de Turing alterna ( ATM ) es una máquina de Turing no determinista ( NTM ) con una regla para aceptar cálculos que generaliza las reglas utilizadas en la definición de las clases de complejidad NP y co-NP . El concepto de cajero automático fue establecido por Chandra y Stockmeyer ^[1] e independientemente por Kozen ^[2] en 1976, con una publicación conjunta en 1981. ^[3]

La definición de NP utiliza el modo de cálculo existencial : si alguna elección conduce a un estado de aceptación, entonces todo el cálculo acepta. La definición de co-NP utiliza el modo universal de cálculo: solo si todas las opciones conducen a un estado de aceptación, se acepta todo el cálculo. Una máquina de Turing alternante (o para ser más precisos, la definición de aceptación para tal máquina) alterna entre estos modos.

Una máquina de Turing alternante es una máquina de Turing no determinista cuyos estados se dividen en dos conjuntos: estados existenciales y estados universales . Un estado existencial es de aceptación si alguna transición conduce a un estado de aceptación; un estado universal es de aceptación si cada transición conduce a un estado de aceptación. (Así, un estado universal sin transiciones acepta incondicionalmente; un estado existencial sin transiciones rechaza incondicionalmente). La máquina en su conjunto acepta si el estado inicial es aceptable.

Formalmente, a (de una sola cinta) máquina alterna Turing es una 5- tupla donde ${\ Displaystyle M = (Q, \ Gamma, \ delta, q_ {0}, g)}$

Si M está en un estado con , se dice que la configuración acepta , y si se dice que se rechaza . Se dice que una configuración con acepta si todas las configuraciones alcanzables en un paso están aceptando, y rechaza si alguna configuración alcanzable en un paso es rechazada. Se dice que una configuración con acepta cuando existe alguna configuración accesible en un paso que acepta y rechaza cuando todas las configuraciones alcanzables en un paso son rechazadas (este es el tipo de todos los estados en una NTM clásica excepto el estado final). Se dice que M acepta una cadena de entrada w si la configuración inicial de ${\ Displaystyle q \ in Q}$ ${\ Displaystyle g (q) = aceptar}$ ${\ Displaystyle g (q) = rechazar}$ ${\ Displaystyle g (q) = \ wedge}$ $g(q)=\vee$ M (el estado de M es , la cabeza está en el extremo izquierdo de la cinta y la cinta contiene w ) acepta y rechaza si la configuración inicial rechaza. $q_{0}$

Tenga en cuenta que es imposible que una configuración acepte y rechace a la vez, sin embargo, algunas configuraciones pueden no aceptar ni rechazar, debido a la posibilidad de cálculos no determinantes.