En informática teórica , una máquina de Turing no determinista ( NTM ) es un modelo teórico de computación cuyas reglas rectoras especifican más de una acción posible en algunas situaciones determinadas. Es decir, el siguiente estado de un 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 .
Las NTM a veces se utilizan en experimentos mentales para examinar las capacidades y 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 la computación no determinista con una computadora determinista.
En esencia, se imagina que una máquina de Turing es una computadora simple que lee y escribe símbolos uno por uno en una cinta interminable siguiendo estrictamente un conjunto de reglas. Determina qué acción debe realizar a continuación según su estado interno y qué símbolo ve actualmente . Un ejemplo de una de las reglas de una máquina de Turing podría ser: "Si estás en el estado 2 y ves una 'A', cámbiala a 'B', muévete hacia la izquierda y cambia al estado 3".
En una máquina de Turing determinista (DTM), el conjunto de reglas prescribe como máximo una acción a realizar 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:
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 hacia la derecha y cambie al estado 5.
A diferencia de 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 en cualquier situación dada. Por ejemplo, una X en la cinta en el estado 3 podría permitir al NTM:
o
¿Cómo "sabe" la MNA cuál de estas medidas debe adoptar? Hay dos maneras de verlo. Una es decir que la máquina es "el adivino más afortunado posible"; siempre elige una transición que eventualmente conduce a un estado de aceptación, si existe tal transición. La otra es imaginar que la máquina se " bifurca " en muchas copias, cada una de las cuales sigue una de las transiciones posibles. Mientras que un DTM tiene una única "ruta de cálculo" que sigue, un NTM tiene un "árbol de cálculo". Si al menos una rama del árbol se detiene con una condición de "aceptación", el NTM acepta la entrada.
Una máquina de Turing no determinista se puede definir formalmente como una tupla de seis , donde
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 sólo una relación.
Las configuraciones y la relación de rendimientos entre 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 la relación de rendimientos 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 un 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 existe) y, de lo contrario, la cinta está en blanco. .
Un NTM acepta una cadena de entrada si y sólo si al menos una de las posibles rutas computacionales a partir de esa cadena pone la máquina en un estado de aceptación. Al simular las numerosas rutas de bifurcación de un NTM en una máquina determinista, podemos detener toda la simulación tan pronto como alguna rama alcance un estado de aceptación.
Como construcción matemática utilizada principalmente en pruebas, existe una variedad de variaciones menores en la definición de NTM, pero todas estas variaciones aceptan lenguajes equivalentes.
El movimiento de la cabeza en la salida de la relación de transición a menudo se codifica numéricamente en lugar de usar letras para representar el movimiento de la cabeza hacia la izquierda (-1), estacionaria (0) y derecha (+1); dando una salida de función de transición de . Es común omitir la salida estacionaria (0), [1] y en su lugar insertar el cierre transitivo de cualquier transición estacionaria deseada.
Algunos autores añaden un estado de rechazo explícito , [2] 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 cada rama debe rechazar para que la cadena sea rechazada.
Cualquier problema computacional que pueda resolverse mediante un DTM también puede resolverse mediante un NTM, y viceversa. Sin embargo, se cree que, en general, la complejidad temporal puede no ser la misma.
Los NTM incluyen a los DTM como casos especiales, por lo que todos los cálculos que puede realizar un DTM también pueden realizarse mediante el NTM equivalente.
Podría parecer que los NTM son más poderosos 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 rama 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.
Un enfoque es utilizar 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 múltiples continuaciones. .
Otra construcción simula NTM con DTM de 3 cintas, de las 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 árbol de cálculo del NTM. [3] Los DTM de 3 cintas se simulan fácilmente con un DTM normal de una sola cinta.
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 creciente de longitud hasta que encuentra uno que acepte. Por lo tanto, la duración de un cálculo de aceptación del DTM es, en general, exponencial en comparación con la duración del cálculo de aceptación más corto del NTM. Se cree que esto es una propiedad general de las simulaciones de MNA mediante MDT. El problema P = NP , la cuestión no resuelta más famosa en informática, se refiere a un caso de esta cuestión: si todo problema solucionable por un NTM en tiempo polinomial es necesariamente solucionable también por un DTM en tiempo polinomial.
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, sólo puede tener un número limitado de configuraciones posibles.
Debido a que las computadoras cuánticas utilizan 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. [4] Sin embargo, los expertos creen (pero no se ha demostrado) 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. [5] [ se necesita mejor fuente ] En particular, es probable que los problemas NP-completos puedan resolverse mediante NTM, pero no mediante computadoras cuánticas en tiempo polinomial.
Intuitivamente hablando, si bien una computadora cuántica puede estar en un estado de superposición correspondiente a todas las ramas computacionales posibles que se han ejecutado al mismo tiempo (similar a un NTM), la medición final colapsará la computadora cuántica en una rama seleccionada al azar. Por lo tanto, esta rama no representa, en general, la solución buscada, a diferencia del NTM, que puede elegir la solución correcta entre las ramas exponencialmente numerosas.
