¿Es el no determinismo en una máquina de turing no determinista diferente de la de los autómatas finitos y los autómatas de empuje?

9

Deje una cadena de entrada como . Luego, si un NFA se encuentra actualmente en el estado r (y ha leído la entrada hasta el alfabeto w i ), antes de leer el siguiente símbolo de entrada, el NFA se divide en dos NFA, uno en el estado r y otro en s , si hay una transición del tipo r ϵ s . Si hay un ciclo del tipo r ϵ s ϵ q 1 . . . . ϵw1w2...wnrwirsrϵs , donde q i son algunos estados de NFA, entonces no sirve de nada recordar otro NFA en el estado r hasta el punto donde se ha leído la entrada hasta el alfabeto w i . Si un PDA (no determinista) está en estado r (y la entrada se lee hasta w i ) y existe un ciclo r ϵ , ϵ a s ϵ , ϵ a q 1 . . . . ϵ , ϵ arϵsϵq1....ϵqkϵrqirwi

rwi (donde la transición ϵ , ϵ a significa que nada después de w i se lee desde la entrada, no sesacanada o se lee desde la pila y el alfabeto a se introduce en la pila) y luego antes de leer el siguiente alfabeto de entrada w i + 1 habrá PDA infinito en estados r , s , q 1 , . . . q krϵ,ϵasϵ,ϵaq1....ϵ,ϵaqkϵ,ϵarϵ,ϵawiawi+1r,s,q1,...qk porque a diferencia del NFA, aunque los estados son contenidos de pila finitos, pueden ser diferentes (posibilidades infinitas), si no me equivoco.

Al igual que con NFA y PDA, el poder del no determinismo proviene de las transiciones . Así que supongo que la máquina de Turing no determinista también obtiene su no determinismo de transiciones ϵ como NFA y PDA (más como PDA). Sé que una máquina de Turing determinista puede simular una no determinista (conozco la prueba que usa la búsqueda de primer pan). Pero ahora tengo dudas sobre cómo es posible. Porque si existe un ciclo del tipo PDA anterior, en el diagrama de estado de la máquina de Turing no determinista, antes de leer el siguiente símbolo w i + 1ϵϵwi+1la máquina de Turing determinista incluso cuando simula una configuración en alguna rama de la máquina de Turing no determinista (mientras que bfs) tendría que hacer un seguimiento de la máquina de Turing infinita (nuevamente los estados son finitos pero los símbolos en la cinta tienen posibilidades infinitas).
Entonces, ¿cómo se define exactamente el no determinismo en el caso de las máquinas de Turing? ¿Estoy malinterpretando algo trivial? ¿Las máquinas de Turing no deterministas usan transiciones ?ϵ


Lamento mis dudas triviales. Si algo es incorrecto, puedo actualizar mi pregunta.

Sashas
fuente
2
con respecto a la pregunta del título, no hay mucha diferencia en las definiciones formales. En cuanto al poder emergente, sí, tiene implicaciones muy diferentes en cada modelo de máquina. En cuanto al resto de la pregunta, resulta difícil de analizar. :(
vzn
1
¿Has revisado Wikipedia? en.wikipedia.org/wiki/Non-deterministic_Turing_machine
Yuval Filmus
@YuvalFilmus, sí. La definición de la función de transición incluye el conjunto de potencia que entiendo. Pero lo que pasa transiciones en las máquinas de Turing todavía no está claro para mí. epsilon
sashas
@vzn, eso creo. Lo siento mucho. Soy malo para plantear mis dudas. Pero puedo mejorar si me das sugerencias.
sashas

Respuestas:

8

El no determinismo es el mismo concepto en todos los contextos: la máquina tiene varias opciones para proceder en cualquier punto dado. Sin embargo, la semántica es un poco diferente, ya que los DFA / NFA y PDA siempre definen funciones totales , mientras que las máquinas Turing (deterministas o no deterministas) en general definen funciones parciales .

Una función parcial es una definida solo en parte del dominio. Si no está definido en x, entonces escribimos f ( x ) = . (Entonces f es realmente una función total, pero hay un elemento especial en el rango que significa que la salida no está definida.) Una máquina determinista de Turing M define una función parcial de la siguiente manera: si M se detiene en x, entonces M ( x ) es el contenido de la cinta cuando M se detiene en x ; y de lo contrario, M ( x ) = fxf(x)=fMMxM(x)MxM(x)=.

Un decisor de máquina de Turing determinista tiene dos tipos de estados de detención, aceptar y rechazar, y define una función parcial de la siguiente manera: si detiene en x en un estado de aceptación, entonces M ( x ) = 1 ; si se detiene en un estado de rechazo, entonces M ( x ) = 0 ; si no se detiene, entonces M ( x ) = . Si M siempre se detiene, entonces decimos que acepta el lenguaje L = { x : M ( xMxM(x)=1M(x)=0M(x)=ML={x:M(x)=1} .

Una máquina de Turing no determinista (que siempre es un decisor) puede "ramificarse" (tener varias opciones posibles en cualquier momento) y tiene la siguiente semántica:

  • si en la entrada x , la máquina M se detiene en todas las ramas, deteniéndose en un estado de aceptación de al menos una rama.M(x)=1xM
  • si en la entrada x , la máquina M se detiene en todas las ramas, siempre deteniéndose en un estado de rechazo.M(x)=0xM
  • si en la entrada x existe una rama en la que M no se detiene.M(x)=xM

Dada esta definición, es de esperar que esté claro cómo simular una máquina de Turing no determinista utilizando un decisor de máquina de Turing determinista: prueba todas las ramas, verificando si alguna de ellas conduce a un estado de detención aceptable. Después de que todas las ramas se hayan detenido, puede decidir si pasar a un estado de aceptación o de rechazo. Si la máquina de Turing no determinista no se detiene en alguna rama, entonces también lo haría la determinista.


¿Qué pasa con los movimientos ? Causan problemas porque el autómata correspondiente podría nunca detenerse. Para autómatas finitos (NFA y PDA) ignoramos silenciosamente los cálculos que no se detienen. Nuestra razón para hacerlo es que los lenguajes resultantes siempre son computables, aunque el ingenuo algoritmo para simularlos de manera determinista (simulando todas las rutas de cálculo) no funciona del todo. Esto no es tan difícil para los NFA, que se pueden convertir a DFA. Sin embargo, los PDA deterministas son estrictamente más débiles que los PDA no deterministas. Sin embargo, puede demostrar que cada PDA es equivalente a uno sin ϵϵϵ transiciones (aunque la prueba podría pasar por gramáticas libres de contexto).

Puede simular movimientos en máquinas Turing, pero debe tener cuidado de que no haya bucles que causen cálculos que no se detengan. En algunos casos, sin embargo, podemos usar el mismo truco que el anterior. Por ejemplo, suponga que su máquina Turing tiene limitaciones de espacio: conocemos un límite superior en el espacio que usa (dependiendo de la longitud de entrada). En ese caso, cada cálculo que no se detiene necesariamente realiza un ciclo (ya que la máquina de Turing tiene muchos estados, incluido el contenido de la cinta) y, por lo tanto, si "ignoramos" los cálculos que no se detienen como se indicó anteriormente, el modelo de cálculo resultante sigue siendo computable. En términos más generales, esto funciona siempre y cuando tengamos la garantía de que cada ciclo de cálculo no se detiene. (Este es el caso de las NFA pero no de las PDA).ϵ

Yuval Filmus
fuente
Gracias. Tuve una última duda. En un PDA con la transición , si el PDA está en el estado r, entonces se dividirá solo si b ( b es el alfabeto leído de la cinta de entrada, c es el alfabeto sacado de la pila y a se empuja a la pila ) es ϵ independientemente de lo que son a y c ( ϵ o alfabetos de pila regulares). Estoy en lo cierto? rb,casrbbcaϵacϵ
sashas
@sasha La ejecución se "divide" cuando hay más de una opción para continuar.
Yuval Filmus
¿Cómo hago para probar que un PDA con transiciones ϵ se puede convertir en uno sin ellas? Sé que siempre puedo probar que el lenguaje aceptado por cualquier PDA es decidible al convertirlo a su CFG en forma Chomsky normal. Pero todavía no se puede convertir a PDA sin transiciones epsilon. Realmente agradecería cualquier pista. ϵ
sashas
1
@sasha Puede convertir una gramática libre de contexto en forma normal de Greibach a un PDA sin transiciones (al menos según Wikipedia). ϵ
Yuval Filmus
1
AaB1B2BnAaAB1BnϵAa