Máquina de Turing no determinista

En informática teórica, una máquina de Turing no determinista (NTM) es un modelo teórico de computación cuyas reglas de gobierno especifican más de una acción posible en determinadas situaciones. Es decir, el siguiente estado de una NTM no está completamente determinado por su acción y el símbolo actual que ve, a diferencia de una máquina de Turing determinista.

Los NTM a veces se usan en experimentos mentales para examinar las capacidades y los límites de las computadoras. Uno de los problemas abiertos más importantes en informática teórica es el problema P versus NP, que (entre otras formulaciones equivalentes) se refiere a la cuestión de cuán difícil es simular computación no determinista con una computadora determinista.

Antecedentes

En esencia, se imagina que una máquina de Turing es una computadora simple que lee y escribe símbolos de uno en uno en una cinta interminable siguiendo estrictamente un conjunto de reglas. Determina qué acción debe realizar a continuación de acuerdo con su estado interno y qué símbolo ve actualmente. Un ejemplo de una de las reglas de la máquina de Turing podría ser: "Si está en el estado 2 y ve una 'A', cámbiela a 'B' 39;, muévase a la izquierda y cambie al estado 3."

Máquina de Turing determinista

En una máquina de Turing determinista (DTM), el conjunto de reglas prescribe como máximo una acción para cualquier situación dada.

Una máquina de Turing determinista tiene una función de transición que, para un estado y símbolo dados debajo del cabezal de la cinta, especifica tres cosas:

• el símbolo a ser escrito a la cinta (puede ser el mismo que el símbolo actualmente en esa posición, o ni siquiera escribir en absoluto, dando lugar a ningún cambio práctico),
• la dirección (izquierda, derecha o ninguna) en la que la cabeza debe moverse, y
• el estado posterior del control finito.

Por ejemplo, una X en la cinta en el estado 3 podría hacer que el DTM escriba una Y en la cinta, mueva el cabezal una posición a la derecha y cambie al estado 5.

Intuición

Comparación de la computación determinista y no determinista

En contraste con una máquina de Turing determinista, en una máquina de Turing no determinista (NTM) el conjunto de reglas puede prescribir más de una acción a realizar para cualquier situación dada.. Por ejemplo, una X en la cinta en el estado 3 podría permitir que la NTM:

• Escribe un Y, mueve a la derecha, y cambia al estado 5

o

• Escribe una X, muévete a la izquierda y quédate en el estado 3.

Resolución de múltiples reglas

¿Cómo "sabe" ¿cuál de estas acciones debe tomar? Hay dos formas de verlo. Una es decir que la máquina es el "adivinador más afortunado posible"; siempre elige una transición que eventualmente conduce a un estado de aceptación, si es que existe tal transición. La otra es imaginar que la máquina "ramifica" en muchas copias, cada una de las cuales sigue una de las transiciones posibles. Mientras que un DTM tiene una sola "ruta de cálculo" de lo que sigue, una NTM tiene un "árbol de cómputo". Si al menos una rama del árbol se detiene con un "aceptar" condición, la NTM acepta la entrada.

Definición

Una máquina Turing no determinista se puede definir formalmente como un seis-tuple ${displaystyle M=(Q,SigmaiotasqcupA,delta)}$, donde

• ${displaystyle Q}$ es un conjunto finito de estados
• ${displaystyle Sigma }$ es un conjunto finito de símbolos (el alfabeto de cinta)
• ${displaystyle iota in Q}$ es el estado inicial
• ${displaystyle sqcup in Sigma }$ es el símbolo en blanco
• ${displaystyle Asubseteq Q}$ es el conjunto de estados de aceptación (final)
• ${displaystyle delta subseteq left(Qbackslash Atimes Sigma right)times left(Qtimes Sigma times {L,S,R}right)}$ es una relación en estados y símbolos llamados relación de transición. ${displaystyle L.$ es el movimiento a la izquierda, ${displaystyle S.$ no es movimiento, y ${displaystyle R.$ es el movimiento a la derecha.

La diferencia con una máquina de Turing estándar (determinista) es que, para las máquinas de Turing deterministas, la relación de transición es una función y no solo una relación.

Las configuraciones y la relación de rendimientos en las configuraciones, que describe las posibles acciones de la máquina de Turing dado cualquier posible contenido de la cinta, son como para las máquinas de Turing estándar, excepto que los rendimientos< /i> la relación ya no tiene un solo valor. (Si la máquina es determinista, los cálculos posibles son todos prefijos de una ruta única, posiblemente infinita).

La entrada para una NTM se proporciona de la misma manera que para una máquina de Turing determinista: la máquina se inicia en la configuración en la que el cabezal de la cinta está en el primer carácter de la cadena (si lo hay) y la cinta se todo en blanco de lo contrario.

Una NTM acepta una cadena de entrada si y solo si al menos una de las posibles rutas computacionales a partir de esa cadena pone a la máquina en un estado de aceptación. Al simular las muchas rutas de bifurcación de un NTM en una máquina determinista, podemos detener toda la simulación tan pronto como cualquier rama alcance un estado de aceptación.

Definiciones alternativas

Como construcción matemática utilizada principalmente en pruebas, hay una variedad de variaciones menores en la definición de una MNA, pero todas estas variaciones aceptan lenguajes equivalentes.

El movimiento cabezal en la salida de la relación de transición es a menudo codificado numéricamente en lugar de utilizar letras para representar mover la cabeza izquierda (-1), estacionario (0) y derecho (+1); dando una función de transición salida de la ${displaystyle left(Qtimes Sigma times {-1,0,+1}right)}$. Es común omitir la salida estacionaria (0) e insertar el cierre transitivo de cualquier transición estacionaria deseada.

Algunos autores agregan un estado de rechazo explícito, lo que hace que la NTM se detenga sin aceptar. Esta definición aún conserva la asimetría que cualquier rama no determinista puede aceptar, pero todas las ramas deben rechazarse para que la cadena sea rechazada.

Equivalencia computacional con DTMs

Cualquier problema computacional que pueda ser resuelto por un DTM también puede ser resuelto por un NTM, y viceversa. Sin embargo, se cree que, en general, la complejidad del tiempo puede no ser la misma.

DTM como caso especial de NTM

Las NTM incluyen a los DTM como casos especiales, por lo que todos los cálculos que puede realizar un DTM también pueden ser realizados por la NTM equivalente.

Simulación DTM de NTM

Puede parecer que los NTM son más potentes que los DTM, ya que pueden permitir árboles de posibles cálculos que surjan de la misma configuración inicial, aceptando una cadena si alguna de las ramas del árbol la acepta. Sin embargo, es posible simular NTM con DTM y, de hecho, esto se puede hacer de más de una manera.

Multiplicidad de estados de configuración

Un enfoque es usar un DTM cuyas configuraciones representan múltiples configuraciones del NTM, y la operación del DTM consiste en visitar cada uno de ellos por turno, ejecutar un solo paso en cada visita y generar nuevas configuraciones. siempre que la relación de transición defina continuaciones múltiples.

Multiplicidad de cintas

Otra construcción simula los NTM con DTM de 3 cintas, de los cuales la primera cinta siempre contiene la cadena de entrada original, la segunda se usa para simular un cálculo particular del NTM y la tercera codifica una ruta en el NTM' árbol de cálculo s. Los DTM de 3 cintas se simulan fácilmente con un DTM normal de una sola cinta.

Complejidad temporal y P versus NP

En la segunda construcción, el DTM construido realiza efectivamente una búsqueda en amplitud del árbol de cálculo del NTM, visitando todos los cálculos posibles del NTM en orden de longitud creciente hasta que encuentra uno que lo acepte. Por lo tanto, la longitud de un cálculo de aceptación del DTM es, en general, exponencial en la longitud del cálculo de aceptación más corto del NTM. Se cree que esto es una propiedad general de las simulaciones de NTM por DTM. El problema P = NP, la pregunta no resuelta más famosa en informática, se refiere a un caso de este problema: si todos los problemas que se pueden resolver con un NTM en tiempo polinomial necesariamente también se pueden resolver con un DTM en tiempo polinomial.

No determinismo acotado

Una NTM tiene la propiedad de no determinismo acotado. Es decir, si un NTM siempre se detiene en una cinta de entrada determinada T, entonces se detiene en un número limitado de pasos y, por lo tanto, solo puede tener un número limitado de configuraciones posibles.

Comparación con ordenadores cuánticos

La forma sospechosa de la gama de problemas solvable por ordenadores cuánticos en tiempo polinomio (BQP). Note que la figura sugiere ${displaystyle {Mathsf {}neq {Mathsf}}$ y ${displaystyle {Mathsf {}neq {Mathsf {f}}$. Si esto no es verdad, entonces la figura debe verse diferente.

Debido a que las computadoras cuánticas usan bits cuánticos, que pueden estar en superposiciones de estados, en lugar de bits convencionales, a veces existe la idea errónea de que las computadoras cuánticas son NTM. Sin embargo, los expertos creen (pero no se ha probado) que el poder de las computadoras cuánticas es, de hecho, incomparable al de las NTM; es decir, es probable que existan problemas que una NTM podría resolver de manera eficiente y que una computadora cuántica no puede y viceversa. En particular, es probable que los problemas NP-completos se puedan resolver con NTM, pero no con computadoras cuánticas en tiempo polinomial.

Intuitivamente hablando, mientras que una computadora cuántica puede estar en un estado de superposición correspondiente a todas las ramas computacionales posibles ejecutadas al mismo tiempo (similar a una NTM), la medición final colapsará la computadora cuántica en una rama seleccionada al azar.. Entonces, esta rama no representa, en general, la solución buscada, a diferencia de la NTM, que puede elegir la solución correcta entre las muchas ramas exponencialmente.