¿Cómo funciona una máquina de Turing no determinista?

12

¿Qué diferencias hay entre las máquinas de Turing deterministas y no deterministas? Modelos diferentes pero equivalentes de NDTM. En particular, ¿cuál es esta frase de uso frecuente "adivinanza no determinista"? Cómo usarlo correctamente y ejemplos de uso incorrecto. Mi objetivo es crear una pregunta de referencia.

fade2black
fuente
1
¿Qué buscas más allá de lo que Wikipedia tiene para decir sobre el tema?
David Richerby
1
Mis contribuciones en este asunto: uno , dos .
Raphael
No estoy seguro de estar de acuerdo con la forma de este intento de una pregunta de referencia (bastante amplia). Además, no está claro para mí qué más allá de la definición se espera aquí. (Si más personas leyeran la definición, habría menos confusión).
Raphael

Respuestas:

8

Aquí hay varias formas de pensar sobre el no determinismo (copiado de esta respuesta ).

El genio. Cada vez que la máquina tiene una opción, un genio le dice qué camino tomar. Si la entrada está en el idioma, entonces el genio puede dirigir la máquina de tal manera que finalmente acepte. Por el contrario, si la entrada no está en el idioma, lo que sea que el genio le diga a la máquina que haga, siempre lo rechazará.

Consejos La máquina calcula una función bivariada. La primera entrada es una palabra.w, y la segunda entrada es una "pista" x. Cada vez que la máquina se enfrenta a una elección no determinista, consulta el siguiente símbolo de pista y funciona en consecuencia. Se nos promete lo siguiente:

  • Integridad: siwL entonces hay alguna pista x lo que hace que la máquina acepte.
  • Solidez: siwL entonces la máquina rechaza todas las pistas.

Aceptando cálculos. Un cálculo de aceptación es un cálculo legal (uno en el que la máquina siempre funciona de acuerdo con una de las opciones que enfrenta) que termina en un estado de aceptación. Una palabra está en el idioma si tiene un cálculo aceptable.

Podemos formalizar la noción de aceptar el cálculo utilizando configuraciones . Una configuración es una descripción instantánea del estado completo de la máquina. Podemos definir una relaciónσσ, dónde σ,σ son configuraciones, que se mantienen cuando σ puede llevar a σen un solo paso En una máquina determinista, hay como máximo unaσ por cada uno σ, mientras que en una máquina no determinista, podría haber más de uno. Un cómputo de aceptación de una palabra.w es uno que comienza en la configuración inicial (la cinta contiene w, la cabeza apunta al comienzo de w, el estado es el estado inicial) y termina en una configuración de aceptación.

Otra descripción equivalente es en términos de accesibilidad. Considere un gráfico dirigido en el que los vértices son configuraciones y hay un borde desdeσ a σ Si σσ. Un cálculo de aceptación es una ruta desde la configuración inicial a una configuración de aceptación.

Yuval Filmus
fuente
7

La diferencia entre las máquinas de Turing deterministas y no deterministas radica en la función de transición. En máquinas deterministas de Turingδ La función de transición es una función parcial:

δ:Q×BQ×B×{left,right}

lo que significa que, dado un estado y un símbolo de cinta, tiene uno o ninguno, ingrese el símbolo a la derecha y la dirección para moverse. Sin embargo, en máquinas Turing no deterministas esto se ve (aquíP es el conjunto de subconjuntos de un conjunto):

δ:Q×BP(Q×B×{left,right})

lo que significa que no tiene ninguno o varios estados, símbolos de cinta para escribir o dirección para moverse. Esto le da a su máquina la posibilidad de elegir efectivamente en tal estado y un símbolo de cinta entre las diferentes "ramas" de cómputo posibles.

En la práctica, esto significa que podemos calcular diferentes salidas para la misma entrada. Por lo tanto, el lenguaje de una máquina de Turing no determinista es el conjunto de palabras para el que encontramos una derivación en las transiciones definidas. Una ejecución específica puede no encontrar dicha derivación, pero lo importante es que puede ocurrir. Entonces, cuando "adivinas", simplemente estás eligiendo una de las posibles ramas de la computación.

Ejemplo de uso

L={(M1,M2):there exists at least one word accepted by both TM at the same time}

En este caso uno podría simplemente "adivinar" una palabra w y ejecutar M1 y M2 en wcomprobando que si ambos aceptan, aceptan al mismo tiempo. La suposición podría funcionar introduciendo un estadoq con transiciones que escriben en alguna cinta 0sy / o 1sy eso sale al leer cualquier símbolo en la máquina general.

Para ser honesto, no he encontrado ningún ejemplo de mal uso de esta "suposición", pero comprobar que cada vez que se usa esta frase se hace correctamente, se reduce para verificar que se pueda construir un autómata con esta estructura que simule la suposición.

Rodrigo
fuente
"En la práctica, esto significa que podemos calcular diferentes salidas para la misma entrada". - Esto parece sugerir que en realidad podríamos construir una máquina no determinista. Eso es falso.
Raphael
@Raphael, ¿quieres decir que no es posible construir una máquina no determinista? por que es el caso
Rodrigo
Porque el no determinismo es un concepto matemático que no tiene un equivalente físico (que yo sepa).
Raphael
6

Aceptación de cadena de entrada en NTM

permítanme agregar más sobre las máquinas de Turing deterministas y no deterministas. Consideremos que para algún idiomaL, diseñamos una máquina de Turing determinista y no determinista respectivamente. En alguna entradax, solo habrá una ruta de configuraciones en el caso de la máquina de Turing determinista, es decir c0c1ck (donde cada ci representa una configuración en ith paso). Ahora en base a la configuraciónck, podemos aceptar y rechazar fácilmente la cadena de entrada x.

Vea la imagen a continuación para una mejor comprensión: ingrese la descripción de la imagen aquí

En el caso de NTM, debemos tener cuidado, porque puede suceder que en algunas rutas de configuración, lleguemos al estado de rechazo. Entonces, para máquinas Turing no deterministas, decimos que se acepta una cadena si al menos una de las rutas de configuración conduce al estado de aceptación . Rechazaremos la cadena de entrada si todas las rutas de configuración conducen al estado de rechazo.

Por ejemplo, considere el árbol de configuración dado anteriormente para la máquina de Turing no determinista en digamos alguna cadena de entrada xEn este caso, aceptaremos la cadena de entrada porque hay una única ruta de aceptación.

Referencia : http://cs.umw.edu/~finlayson/class/fall14/cpsc326/notes/24-complexity2.html

Shiv
fuente
5

Aumento con un módulo de adivinanzas.

Encontré este modelo en " Computadoras e Intractabilidad " de MR Garey y DS Johnson.

El NDTM tiene exactamente la misma estructura que un DTM, excepto que se aumenta con un módulo de adivinanzas que tiene su propio cabezal de solo escritura. El módulo de adivinanzas proporciona los medios para escribir la "conjetura" y se utiliza únicamente para este propósito.

ingrese la descripción de la imagen aquí

Cómo funciona.

La primera etapa es la etapa de adivinanzas. Inicialmente, la cadena de entradax está escrito en cuadrados de cinta 1 mediante |x| (mientras que todos los otros cuadrados están en blanco), el cabezal de lectura-escritura escanea el cuadrado 1, el cabezal de solo escritura está escaneando cuadrado 1, y el control de estado finito está "inactivo". El módulo de adivinanzas luego dirige la cabeza de solo escritura, un paso a la vez, ya sea para escribir algún símbolo del alfabeto de la cinta Γ en el cuadrado de la cinta que se está escaneando y mueva un cuadrado hacia la izquierda, o para detenerse, momento en el cual el módulo de adivinanzas queda inactivo y el control de estado finito se activa en estado q0. La elección de si permanecer activo y, si es así, qué símbolo deΓescribir, lo realiza el módulo de adivinanzas de manera totalmente arbitraria. Por lo tanto, el módulo de adivinanzas puede escribir cualquier cadena desdeΓ antes de detenerse y, de hecho, nunca es necesario detenerse.

La etapa de "verificación" comienza cuando el control de estado finito se activa en estado q0. A partir de este momento, el cálculo se realiza únicamente bajo la dirección del programa NDTM de acuerdo con exactamente las mismas reglas que para un DTM. El módulo de adivinanzas y su cabeza de solo escritura ya no están involucrados, ya que han cumplido su función escribiendo la cadena adivinada en la cinta. Por supuesto, la cadena adivinada puede (y generalmente será) examinada durante la etapa de verificación. El cálculo cesa cuando y si el control de estado de estado finito entra en uno de los dos estados de detención (ya seaqY o qN) y se dice que acepta el cálculo si se detiene en el estadoqY. Todos los demás cálculos, detenidos o no, se clasifican juntos simplemente como cálculos no aceptables .
Tenga en cuenta que cualquier programa NDTMM tendrá un número infinito de cálculos posibles para una cadena de entrada dada x, uno para cada posible cadena adivinada de Γ. Decimos que el programa NDTMM acepta x si al menos uno de estos es un cálculo de aceptación.

El tiempo requerido por un programa NDTMM aceptar la cuerda xLM se define como el mínimo, sobre todos los cálculos aceptables de M para x , del número de pasos que ocurren en las etapas de adivinar y verificar hasta el estado de detención qY es ingresado.

El único punto que merece una mención especial especial es que, donde generalmente imaginamos un algoritmo no determinista como adivinar una estructura S que de alguna manera depende de la instancia [problema] dada I, el módulo de adivinanzas de un NDTM ignora por completo la entrada dada. Sin embargo, dado que cada cadena deΓes una suposición posible, siempre podemos diseñar nuestro programa NDTM para que la etapa de verificación comience verificando si la cadena adivinada no corresponde (bajo la interpretación implícita que nuestro programa coloca en las cadenas) a una suposición apropiada para la entrada dada. Si no, el programa puede ingresar inmediatamente al estado de detenciónqN.

. . .

La clase NP se define informalmente como la clase de todos los problemas de decisión Π eso, bajo esquemas de codificación razonables, puede resolverse mediante algoritmos no deterministas de tiempo polinómico.

El uso del término "resolver" en estas definiciones informales, por supuesto, debe tomarse con un grano de sal. Debería ser evidente que un "algoritmo no determinista de tiempo polinómico" es básicamente un dispositivo de definición para capturar la noción de verificabilidad del tiempo polinómico, en lugar de un método realista para resolver problemas de decisión. En lugar de tener solo un cálculo posible en una entrada dada, tiene muchos diferentes, uno para cada posible suposición.

Es esta noción del tiempo polinómico "verificabilidad" que la clase NPestá destinado a aislar. Tenga en cuenta que la verificabilidad del tiempo polinomial no implica la solubilidad polinómica.

fade2black
fuente