Máquina de Turing alternante

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda
Sistema combinacional Autómata finito Autómata con pila Máquina de Turing Teoría de autómatasTeoría de autómatas.svg
Acerca de esta imagen


En la teoría de la complejidad computacional, una máquina de Turing alternante (ATM) es una máquina de Turing no determinista (NTM) con una regla para la aceptación de cómputos que generaliza las reglas usadas en la definición de las clases de complejidad NP y co-NP. El concepto de una ATM fue establecido por Chandra y Stockmeyer en 1976 (ver referencias).

Definiciones[editar]

Descripción informal[editar]

La definición de NP usa el modo existencial de computación: Si cualquier elección lleva a un estado de aceptación, entonces la computación completa acepta. La definición de co-NP usa el modo universal de computación: sólo si todas las opciones llevan a un estado de aceptación, la computación completa acepta. Una máquina de Turing alternante (o para ser más precisos, la definición de la aceptación de 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 grupos: estados existenciales y estados universales. Un estado existencial está aceptando si alguna transición conduce a un estado de aceptación; un estado universal está aceptando si cada transición conduce a un estado de aceptación. (Por lo tanto un estado universal con transiciones acepta incondicionalmente, un estado existencial sin transiciones rechaza incondicionalmente). La máquina como un conjunto acepta si el estado inicial está aceptando.

Definición formal[editar]

Formalmente, una máquina de Turing alternante (de una cinta) es una 5 tupla M=(Q,\Gamma,\delta,q_0,g) donde

  • Q es el conjunto finito de estados
  • \Gamma es el alfabeto finito de la cinta
  • \delta:Q\times\Gamma\rightarrow\mathcal{P}(Q\times\Gamma\times\{L,R\}) es llamada la función de transición (L desplaza la cabeza a la izquierda y R desplaza la cabeza a la derecha)
  • q_0\in Q es el estado inicial
  • g:Q\rightarrow\{\wedge,\vee,acepta,rechaza\} especifica el tipo de cada estado


Si M es un estado q\in Q con g(q)=acepta entonces esa configuración se dice que es aceptante, y si g(q)=rechaza la configuración se dice que es rechazante. Una configuración con g(q)=\wedge se dice que es aceptante si todas las configuraciones en un solo paso son aceptantes, y rechazante si alguna configuración accesible en un solo paso es rechazante. Una configuración con g(q)=\vee se dice que es aceptante cuando existe alguna configuración accesible en un solo paso que es aceptante y recrechazante cuando todas las configuraciones en un solo paso son rechazantes (este es el tipo de todos los estados en una NTM). Se dice que M acepta una cadena de entrada w si la configuración inicial de M es aceptante (el estado de M es q_0, la cabeza está en el extremo izquierdo de la cinta y la cinta contiene w), y rechaza si la configuración inicial es rechazante.

Límites de los recursos[editar]

Cuando se decide si una configuración de una ATM está aceptando o rechazando usando la definición anterior, no es necesario examinar todas las configuraciones accesibles a partir de la configuración actual. En particular, una configuración existencial puede etiquetarse como aceptante si se encuentra cualquier configuración sucesora aceptante, y una configuración universal puede ser etiquetada como rechazante si se encuentra que cualquier configuración sucesora es rechazante.

Una ATM decide un lenguaje formal en el t(n) si al examinar las configuraciones en cualquier entrada de longitud nsólo hasta a t(n) pasos, es suficiente para etiquetar la configuración inicial como aceptante o rechazante. Una ATM decide un lenguaje en el espacio s(n) si es suficiente examinar, desde la izquierda, las configuraciones que no modifican las celdas de la cinta, más allá de la celda s(n).

Un lenguaje que es decidido por algunas ATM en tiempo c\cdot t(n) para alguna constante c>0 se dice que está en la clase {\rm ATIME}(t(n)), y un lenguaje decidido en el espacio c\cdot s(n) se dice que está en la clase {\rm ASPACE}(s(n)).

Referencias[editar]

Véase también[editar]