Máquina de Turing no determinista
La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 8 de enero de 2022; las comprobaciones requieren 5 ediciones .Una máquina de Turing no determinista (NMT) es una máquina de Turing cuya función de transición es un autómata infinito no determinista .
Dispositivo
Una máquina de Turing determinista (ordinaria, clásica) tiene una función de transición que, mediante la combinación del estado actual y el carácter de la cinta, determina tres elementos: el carácter que se escribirá en la cinta, la dirección en la que se moverá la cabeza la cinta y el nuevo estado de la máquina de estado. Por ejemplo, Xen una cinta, el estado 3define de forma única una transición al estado 4, escribiendo un carácter en la cinta Yy moviendo la cabeza una posición hacia la izquierda.
En el caso de una máquina de Turing no determinista, la combinación del estado actual del autómata y el símbolo en la cinta puede permitir varias transiciones a los siguientes estados simultáneamente en paralelo. Por ejemplo, Xen cinta y estado, 3permite tanto un estado 4con un carácter escrito en la cinta Yy un desplazamiento de la cabeza hacia la derecha, como un estado 5con un carácter escrito en la cinta Zy un desplazamiento de la cabeza hacia la izquierda. Por lo tanto, una máquina de Turing no derivada puede estar en muchos estados al mismo tiempo.
A diferencia de una máquina de Turing determinista, que tiene una única "ruta de cálculo", la versión no determinista tiene un "árbol de cálculo" (en general, un número exponencial de rutas). Se dice que una máquina de Turing no determinista acepta entradas si alguna rama del árbol se detiene en un estado de aceptación; de lo contrario, HMT no acepta entradas. (Por lo tanto, las respuestas "sí" y "no" en el caso de cálculos no deterministas no son simétricas).
Definición
Formalmente, una máquina de Turing no determinista se define como seis elementos ordenados de algunos conjuntos: , donde:
- es un conjunto finito de estados
- — conjunto finito de caracteres (alfabeto de cinta)
- - estado inicial
- - carácter de espacio ( )
- es un conjunto finito de estados de aceptación
- es un mapeo multivaluado de un par de estado-símbolo, llamado función de transición.
Equivalencia con una máquina de Turing determinista
A pesar del poder aparentemente mayor de las máquinas no deterministas debido al hecho de que realizan varios cálculos posibles a la vez (requiriendo solo que al menos uno de ellos termine en un estado de aceptación), cualquier lenguaje permitido por una máquina de Turing no determinista también está permitido por una máquina de Turing determinista ordinaria, porque puede simular cualquier transición no determinista, haciendo múltiples copias del estado si se encuentra una ambigüedad.
Modelar el no determinismo requiere mucho más tiempo, la cuestión de estimar la diferencia de costes está abierta: en el caso particular de un límite de tiempo en forma de polinomio de la longitud de la entrada, esta cuestión es el problema clásico " P = NP ".
La clase de algoritmos que se ejecutan en tiempo polinomial en máquinas de Turing no deterministas se denomina clase NP .
Ejemplo
Considere el problema de comprobar que un número entero de b bits N ( 2 b-1 ≤N <2 b ) es compuesto . Entonces b es la longitud de los datos de entrada, en relación con la cual se considera el tiempo de cálculo . La respuesta "SÍ" es un número compuesto y "NO" es un número primo . Esta tarea es complementaria a la prueba de primalidad .
Un algoritmo no determinista para esta tarea podría ser, por ejemplo, el siguiente:
- Elija un entero no determinista m tal que 1<m<N .
- Dividir N por m , denotemos el resto por a .
- Si a=0, responda "SÍ" ( entonces m es un divisor de N ), de lo contrario, responda "NO".
(El algoritmo no está escrito directamente como una definición de una máquina de Turing).
En el tiempo de cálculo de este algoritmo, la parte que define es el tiempo de división, que se puede hacer en O (b 2 ) pasos, que es el tiempo polinomial . Entonces la tarea está en la clase NP .
Para implementar tal tiempo de cálculo, es necesario elegir el número m con éxito o realizar cálculos a lo largo de todos los caminos posibles (para todos los m posibles ) simultáneamente en muchas copias de la máquina.
Si simula este algoritmo en una máquina de Turing determinista, probando todas las opciones posibles a su vez, necesita verificar las ramas N-2=O(2 b ) . Por lo tanto, el tiempo total de cálculo será O(b 2 2 b ) pasos, que ya es un tiempo exponencial , que es significativamente más largo que el tiempo polinomial. Por lo tanto , este algoritmo no cae en la clase P. (Sin embargo, se pueden aplicar otros algoritmos más rápidos para este problema que se ejecutan en tiempo polinomial y, por lo tanto, el problema cae en la clase P).
Literatura
- John Hopcroft, Rajeev Motwani, Jeffrey Ullman. Introducción a la teoría de autómatas, lenguajes y computación. - M. : "Williams" , 2002. - 528 p. - ISBN 0-201-44124-1 .
- Karpov Yu. G. Teoría de los autómatas. - Pedro, 2003. - ISBN 5-318-00537-3 .
| máquina de Turing | |
|---|---|
| Opciones de máquina |
|