Máquina de Turing no determinista - Nondeterministic Turing machine

En la informática teórica , una máquina de Turing no determinista ( NTM ) es un modelo teórico de cálculo 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 .

Las MNA 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.

Fondo

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 sin fin 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 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."

Máquina de Turing determinista

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:

el símbolo que se va a escribir en la cinta (puede ser el mismo que el símbolo actualmente en esa posición, o ni siquiera escribir en absoluto, lo que no implica ningún cambio práctico),
la dirección (izquierda, derecha o ninguna) en la que debe moverse la cabeza, y
el estado subsiguiente 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 hacia la derecha y cambie al estado 5.

Intuición

Comparación de 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:

Escriba una Y, muévase a la derecha y cambie al estado 5

o

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

Resolución de múltiples reglas

¿Cómo "sabe" la NTM cuál de estas acciones debe tomar? Hay dos formas de verlo. Uno 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 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 posibles transiciones. 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 "aceptar", la NTM acepta la entrada.

Definición

Una máquina de Turing no determinista se puede definir formalmente como una tupla de seis , donde ${\ Displaystyle M = (Q, \ Sigma, \ iota, \ sqcup, A, \ delta)}$

${\ 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 A \ subseteq Q}$ es el conjunto de estados de aceptación (final)
${\ Displaystyle \ delta \ subseteq \ left (Q \ backslash A \ times \ Sigma \ right) \ times \ left (Q \ times \ Sigma \ times \ {L, S, R \} \ right)}$ es una relación de estados y símbolos llamada relación de transición . es el movimiento a la izquierda, no hay movimiento y es el movimiento a la derecha. ${\ Displaystyle L}$ ${\ Displaystyle S}$ ${\ Displaystyle R}$

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 dados los posibles contenidos de la cinta, son como para las máquinas de Turing estándar, excepto que la relación de rendimientos ya no es de 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 está 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 una NTM en una máquina determinista, podemos detener toda la simulación tan pronto como cualquier bifurcación alcance un estado de aceptación.

Definiciones alternativas

Como construcción matemática utilizada principalmente en las demostraciones, existe 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 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) y, en su lugar, insertar el cierre transitivo de cualquier transición estacionaria deseada. ${\ Displaystyle \ left (Q \ times \ Sigma \ times \ {- 1,0, + 1 \} \ right)}$

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 puede aceptar cualquier rama no determinista, pero cada rama debe rechazar para que la cadena sea rechazada.

Equivalencia computacional con DTM

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 MNA incluyen a las 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

Podría parecer que las NTM son más poderosas que las 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 MNA con DTM y, de hecho, esto se puede hacer de más de una forma.

Multiplicidad de estados de configuración

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. .

Multiplicidad de cintas

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 de la NTM y la tercera codifica una ruta en el árbol de cálculo de la NTM. Los DTM de 3 cintas se simulan fácilmente con un DTM normal de una sola cinta.

Complejidad del tiempo y P versus NP

En la segunda construcción, el DTM construido realiza efectivamente una búsqueda en amplitud del árbol de cálculo de la NTM, visitando todos los cálculos posibles de la NTM en orden de longitud creciente hasta encontrar uno aceptable. 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 esta es una propiedad general de las simulaciones de MNA mediante DTM. El problema P = NP , la cuestión no resuelta más famosa de la informática, se refiere a un caso de esta cuestión: si todos los problemas que se pueden resolver con una NTM en tiempo polinomial también se pueden resolver necesariamente con una DTM en tiempo polinomial.

No determinismo limitado

Una NTM tiene la propiedad de no determinismo acotado. Es decir, si un NTM siempre se detiene en una determinada cinta de entrada 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 las computadoras cuánticas

La forma sospechosa de la gama de problemas que pueden resolver las computadoras cuánticas en tiempo polinomial (BQP). Tenga en cuenta que la figura sugiere y . Si esto no es cierto, la figura debería verse diferente.

{\ Displaystyle {\ mathsf {P}} \ neq {\ mathsf {NP}}}

{\ Displaystyle {\ mathsf {NP}} \ neq {\ mathsf {PSPACE}}}

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 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. En particular, es probable que los problemas NP-completos se puedan resolver con NTM, pero no con computadoras cuánticas en tiempo polinomial.

Hablando intuitivamente, mientras que una computadora cuántica puede estar en un estado de superposición correspondiente a todas las posibles ramas computacionales que se han ejecutado 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.

Ver también

Máquina probabilística de Turing

Referencias

Martin, John C. (1997). "Sección 9.6: Máquinas de Turing no deterministas". Introducción a los lenguajes y la teoría de la computación (2ª ed.). McGraw-Hill. págs. 277-281. ISBN 978-0073191461.
Papadimitriou, Christos (1993). "Sección 2.7: Máquinas no deterministas". Complejidad computacional (1ª ed.). Addison-Wesley. págs. 45–50. ISBN 978-0201530827.

Languages

In other projects