Volvamos a las definiciones. En la superficie, las dos nociones de máquina de Turing se parecen mucho. Una máquina de Turing determinista es una tupla de 7
[matemáticas] (Q, \ Sigma, \ Gamma, \ delta, q_0, q_ {acc}, q_ {rej}) [/ matemáticas]
donde [matemática] Q [/ matemática] es un conjunto finito de estados , [matemática] \ Sigma [/ matemática] es el alfabeto de entrada, [matemática] \ Gamma [/ matemática] es el alfabeto de cinta (donde [matemática] \ Sigma \ subset \ Gamma [/ math], ya que el símbolo en blanco debe aparecer en [math] \ Gamma [/ math] y no es un símbolo de entrada), [math] \ delta [/ math] es la función de transición, [math] q_0 \ en Q [/ matemática] es el estado inicial y [matemática] q_ {acc} \ en Q [/ matemática] y [matemática] q_ {rej} \ en Q [/ matemática] son los estados de aceptación y rechazo , respectivamente .
- ¿Qué procesos se modelan mejor mediante una distribución exponencial? ¿Cómo se relaciona la función exponencial con tales procesos?
- ¿Cómo debo aprender matemáticas para el algoritmo de programación?
- Cómo convertir una combinación dada a un solo número
- Cómo encontrar un circuito de Euler en un gráfico en tiempo lineal
- ¿Es la 'prueba' del teorema de Demorgan dada en los libros de texto una 'prueba' o una 'verificación'?
Una máquina de Turing no determinista es también una tupla de 7
[matemáticas] (Q, \ Sigma, \ Gamma, \ delta, q_0, q_ {acc}, q_ {rej}) [/ matemáticas]
y las entidades representan lo mismo que en lo anterior con una excepción importante:
En el caso de una máquina de Turing determinista, la función de transición tiene funcionalidad
[matemáticas] \ delta: Q \ times \ Gamma \ rightarrow Q \ times \ Gamma \ times \ {L, R \} [/ math]
Entonces, aplicando [math] \ delta [/ math] a un par de símbolo de estado [math] (q, a) [/ math] obtenemos un triple de la forma [math] (q ‘, a’, L) [ / math] o [math] (q ‘, a’, R) [/ math]. Esto debe interpretarse como: Si la máquina está en estado [matemática] q [/ matemática] y su cabeza lee el símbolo, la máquina ahora pasa al estado [matemática] q ‘[/ matemática] y reemplaza [matemática] a [ / math] por [math] a ‘[/ math] y mueve su cabeza hacia la izquierda (respectivamente, hacia la derecha).
En otras palabras, el comportamiento de una máquina de Turing determinista no es ramificado: dado un estado y un símbolo, solo es posible un siguiente paso.
Una máquina determinista de Turing acepta su entrada si puede, al aplicar la función de transición, eventualmente alcanzar el estado de aceptación [math] q_ {acc} [/ math]. Si la máquina finalmente alcanza el estado [matemática] q_ {rej} [/ matemática], la rechaza. Tenga en cuenta que, por lo tanto, una máquina para algunas cadenas de entrada no acepta ni rechaza.
En el caso de una máquina de Turing no determinista , la función de transición tiene funcionalidad
[matemáticas] \ delta: Q \ times \ Gamma \ rightarrow \ mathcal {P} (Q \ times \ Gamma \ times \ {L, R \}) [/ math]
(Aquí la notación [math] \ mathcal {P} (S) [/ math] denota el conjunto de potencia de un conjunto [math] S [/ math], es decir, la familia de todos los subconjuntos del conjunto [math] S .[/mates])
Aquí, al aplicar [math] \ delta [/ math] a un par de símbolo de estado [math] (q, a) [/ math] obtenemos un conjunto de triples donde cada triple de la forma [math] (q ‘, a ‘, L) [/ math] o [math] (q’, a ‘, R) [/ math]. Esto debe interpretarse como: Si la máquina está en estado [matemática] q [/ matemática] y su cabeza lee el símbolo, la máquina ahora puede realizar cualquiera de los pasos indicados por un triple en este conjunto. Tenga en cuenta que el conjunto de sucesores triples puede estar vacío, por lo que en algunos casos la máquina no puede continuar.
Por lo tanto, el comportamiento de una máquina de Turing no determinista es ramificado : dado un estado y un símbolo, puede ser posible más de un paso siguiente (o ninguno).
La diferencia de aceptación, por lo tanto, tiene que ser ligeramente diferente.
Una máquina de Turing no determinista acepta su entrada si puede, aplicando la función de transición, eventualmente alcanza el estado de aceptación [math] q_ {acc} [/ math]. Entonces, siempre que una elección de pasos conduzca a una eventual aceptación, entonces la máquina acepta su entrada. Si la máquina finalmente alcanza el estado [math] q_ {rej} [/ math] sin importar qué rama se elija, rechaza su entrada . En otras palabras, para que la máquina rechace su entrada, cada elección de pasos debe conducir a un eventual rechazo.
