¿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.
turing-machines
nondeterminism
fade2black
fuente
fuente
Respuestas:
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:
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.
fuente
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:
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):
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
En este caso uno podría simplemente "adivinar" una palabraw y ejecutar M1 y M2 en w comprobando que si ambos aceptan, aceptan al mismo tiempo. La suposición podría funcionar introduciendo un estadoq con transiciones que escriben en alguna cinta 0 sy / o 1 sy 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.
fuente
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 c0⟶c1⟶⋯⟶ck (donde cada ci representa una configuración en i th 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:
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 entradax En 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
fuente
Aumento con un módulo de adivinanzas.
Encontré este modelo en " Computadoras e Intractabilidad " de MR Garey y DS Johnson.
Cómo funciona.
. . .
fuente