En informática teórica , una máquina de Turing no determinista ( MTN ) 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 MTN 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 se utilizan a veces en experimentos mentales para examinar las capacidades y los límites de las computadoras. Uno de los problemas abiertos más importantes en la 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 un cálculo 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 a la vez en una cinta infinita siguiendo estrictamente un conjunto de reglas. Determina qué acción debe realizar a continuación según su estado interno y el símbolo que ve en ese momento . 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 a 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 en cualquier situación dada.
Una máquina de Turing determinista tiene una función de transición que, para un estado y símbolo determinados 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 ( MNT ) 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 que la MNT:
o
¿Cómo sabe la máquina NTM cuál de estas acciones debe realizar? Hay dos formas de verlo. Una es decir que la máquina es la "adivinadora más afortunada 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 " ramifica " en muchas copias, cada una de las cuales sigue una de las transiciones posibles. Mientras que una DTM tiene una única "ruta de cálculo" que sigue, una NTM tiene un "árbol de cálculo". Si al menos una rama del árbol se detiene con una condición de "aceptación", la NTM acepta la entrada.
Una máquina de Turing no determinista se puede definir formalmente como una sextupla , 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 solo una relación.
Las configuraciones y la relación de rendimientos sobre las configuraciones, que describe las posibles acciones de la máquina de Turing dado cualquier contenido posible de la cinta, son como las de las máquinas de Turing estándar, excepto que la relación de rendimientos ya no es univaluada. (Si la máquina es determinista, los cálculos posibles son todos prefijos de una única ruta, 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 hay alguna) y la cinta está completamente en blanco en caso contrario.
Una máquina determinista acepta una cadena de entrada si y solo si al menos una de las posibles rutas computacionales que parten de esa cadena pone a la máquina en un estado de aceptación. Al simular las múltiples rutas de ramificación de una máquina determinista, podemos detener toda la simulación tan pronto como alguna de las ramificaciones alcance un estado de aceptación.
Como construcción matemática utilizada principalmente en demostraciones, hay una variedad de variaciones menores en la definición de una NTM, pero todas estas variaciones aceptan lenguajes equivalentes.
El movimiento de la cabeza en la salida de la relación de transición se suele codificar numéricamente en lugar de usar letras para representar el movimiento de la cabeza hacia la izquierda (-1), estacionaria (0) y hacia la derecha (+1); lo que da como resultado una función de transición de . Es habitual 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 de 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.
Las NTM incluyen a los DTM como casos especiales, por lo que cada cálculo que puede realizar un DTM también puede ser realizado por la NTM equivalente.
Puede parecer que los NTM son más potentes que los DTM, ya que permiten crear árboles de posibles cálculos a partir 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 una de ellas 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 utiliza 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 de una sola cinta normal.
En la segunda construcción, el DTM construido realiza efectivamente una búsqueda en amplitud del árbol de cómputo del NTM, visitando todos los cómputos posibles del NTM en orden de longitud creciente hasta que encuentra uno que lo acepte. Por lo tanto, la longitud de un cómputo que acepte el NTM es, en general, exponencial en la longitud del cómputo que acepte el NTM más corto. Se cree que esta es una propiedad general de las simulaciones de NTM por DTM. El problema P = NP , la pregunta sin resolver más famosa en informática, se refiere a un caso de esta cuestión: si todo problema solucionable por un NTM en tiempo polinómico es necesariamente solucionable también por un DTM en tiempo polinómico.
Un NTM tiene la propiedad de no determinismo acotado, es decir, si un NTM siempre se detiene en una cinta de entrada T dada , entonces se detiene en un número acotado de pasos y, por lo tanto, solo puede tener un número acotado 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 que una computadora cuántica no puede y viceversa. [5] [ se necesita una mejor fuente ] En particular, es probable que los problemas NP-completos sean solucionables por NTM pero no por computadoras cuánticas en tiempo polinomial.
Intuitivamente hablando, si bien un ordenador cuántico puede estar en un estado de superposición correspondiente a todas las posibles ramas computacionales ejecutadas al mismo tiempo (similar a un NTM), la medición final colapsará el ordenador cuántico en una rama seleccionada aleatoriamente. Esta rama, en general, no representa la solución buscada, a diferencia del NTM, al que se le permite elegir la solución correcta entre las muchas ramas exponenciales.
