Hispanopedia Wiki
Articulo de referencia

Máquina de Turing no determinista

En informática teórica y teoría computacional , una máquina de Turing no determinista ( MNT ) es un modelo teórico de computación cuyas reglas especifican más de una acción posi...

Hispanopedia WikiContenido en espanolLectura gratuita

En informática teórica y teoría computacional , una máquina de Turing no determinista ( MNT ) es un modelo teórico de computación cuyas reglas especifican más de una acción posible en determinadas situaciones. Es decir, el siguiente estado de una MNT no está completamente determinado por su acción y el símbolo actual que percibe, a diferencia de la máquina de Turing determinista estándar .

Los modelos de teoría de la computación no determinista ( NTM, por sus siglas en inglés) se utilizan a veces en experimentos mentales para examinar las capacidades y limitaciones de las computadoras. Uno de los problemas abiertos más importantes en la informática teórica es el problema P versus NP , que (entre otras formulaciones equivalentes) se refiere a la dificultad de simular la computación no determinista con una computadora determinista.

Fondo

Alan Turing desarrolló por primera vez el concepto de máquina de Turing en 1936, imaginándola como una computadora simple que lee y escribe símbolos en una cinta continua, uno a la vez, siguiendo estrictamente un conjunto de reglas predefinidas. Determina qué acción debe realizar a continuación según su estado interno y el símbolo que ve en ese momento . Un ejemplo de una de las reglas de una máquina de Turing podría ser: "Si estás en el estado 2 y ves una 'A', cámbiala a 'B', muévete a la izquierda y pasa al estado 3".

Máquina de Turing determinista

En una máquina de Turing determinista (MTD), el conjunto de reglas prescribe como máximo una acción a realizar para cualquier situación dada. Dicha máquina tiene una función de transición que, para un estado y un símbolo dados bajo el cabezal de la cinta, especifica tres cosas:

  • el símbolo que se va a escribir en la cinta (puede ser el mismo que el símbolo que se encuentra actualmente en esa posición, o incluso no escribirse en absoluto, lo que no produce ningún cambio práctico),
  • la dirección (izquierda, derecha o ninguna) en la que debe moverse la cabeza, y
  • el estado subsiguiente del control finito.

Por ejemplo, una X en la cinta en el estado 3 podría hacer que el DTM escriba una Y en la cinta, mueva el cabezal una posición a la derecha y cambie al estado 5.

Descripción

Comparación de la computación determinista y no determinista

A diferencia de una máquina de Turing determinista, en una máquina de Turing no determinista ( MNT ) el conjunto de reglas puede prescribir más de una acción a realizar para cualquier situación dada. Por ejemplo, una X en la cinta en el estado 3 podría permitir a la MNT:

  • Escribe una Y, muévete a la derecha y cambia al estado 5.

o

  • Escribe una X, muévete a la izquierda y permanece en el estado 3.

Dado que una situación determinada puede dar lugar a múltiples acciones, la NTM puede seguir varias secuencias de pasos posibles a partir de una entrada dada. Si al menos una de estas secuencias posibles conduce a un estado de "aceptación", se dice que la NTM acepta la entrada. Mientras que una DTM sigue una única "ruta de cálculo", una NTM tiene un " árbol de cálculo ".

Definición formal

Una máquina de Turing no determinista puede definirse formalmente como una séxtupla.METRO=(Q,Σ,yo,⊔,A,δ){\displaystyle M=(Q,\Sigma ,\iota ,\sqcup ,A,\delta )}, dónde

  • Q{\displaystyle Q}es un conjunto finito de estados
  • Σ{\displaystyle \Sigma }es un conjunto finito de símbolos (el alfabeto de la cinta)
  • yo∈Q{\displaystyle \iota \in Q}es el estado inicial
  • ⊔∈Σ{\displaystyle \sqcup \in \Sigma }es el símbolo en blanco
  • A⊆Q{\displaystyle A\subsetq Q}es el conjunto de estados de aceptación (finales)
  • δ⊆(Q∖A×Σ)×(Q×Σ×{L,S,R}){\displaystyle \delta \subseteq \left(Q\backslash A\times \Sigma \right)\times \left(Q\times \Sigma \times \{L,S,R\}\right)}es una relación entre estados y símbolos llamada relación de transición .L{\displaystyle L}es el movimiento hacia la izquierda,S{\displaystyle S}no hay movimiento, yR{\displaystyle R}es el movimiento hacia la derecha.

La diferencia con una máquina de Turing estándar (determinista) es que, para las máquinas de Turing deterministas, la relación de transición es una función en lugar de simplemente una relación.

Las configuraciones y la relación de rendimientos sobre las configuraciones, que describe las posibles acciones de la máquina de Turing dado cualquier contenido posible de la cinta, son iguales a las de las máquinas de Turing estándar, con la excepción de que la relación de rendimientos ya no es unívoca. (Si la máquina es determinista, todos los cálculos posibles son prefijos de una única ruta, posiblemente infinita).

La entrada para una NTM se proporciona de la misma manera que para una máquina de Turing determinista: la máquina se inicia en la configuración en la que el cabezal de la cinta está en el primer carácter de la cadena (si lo hay), y la cinta está completamente en blanco en caso contrario.

Una máquina de Turing no lineal (NTM) acepta una cadena de entrada si y solo si al menos una de las posibles rutas computacionales que parten de esa cadena lleva a la máquina a un estado de aceptación. Al simular las múltiples ramificaciones de una NTM en una máquina determinista, podemos detener la simulación completa en cuanto cualquier rama alcance un estado de aceptación.

Definiciones alternativas

Como construcción matemática utilizada principalmente en demostraciones, existen diversas variaciones menores en la definición de un NTM, pero todas estas variaciones aceptan lenguajes equivalentes.

El movimiento de la cabeza en la salida de la relación de transición a menudo se codifica numéricamente en lugar de usar letras para representar el movimiento de la cabeza hacia la izquierda (-1), estacionaria (0) y derecha (+1); lo que da como resultado una función de transición de salida de(Q×Σ×{−1,0,+1}){\displaystyle \left(Q\times \Sigma \times \{-1,0,+1\}\right)}. Es común omitir la salida estacionaria (0), [ 1 ] y en su lugar insertar el cierre transitivo de cualquier transición estacionaria deseada.

Algunos autores añaden un estado de rechazo explícito, [ 2 ] que hace que la NTM se detenga sin aceptar. Esta definición aún conserva la asimetría de que cualquier rama no determinista puede aceptar, pero todas las ramas deben rechazar para que la cadena sea rechazada.

Equivalencia computacional con DTM

Cualquier problema computacional que pueda resolverse mediante una DTM también puede resolverse mediante una NTM, y viceversa. Sin embargo, se cree que, en general, la complejidad temporal puede no ser la misma.

DTM como caso especial de NTM

Las NTM incluyen a las DTM como casos especiales, por lo que cualquier cálculo que pueda realizar una DTM también puede ser realizado por la NTM equivalente.

Simulación DTM de NTM

Podría parecer que las NTM son más potentes que las DTM, ya que permiten la creación de árboles de posibles cálculos a partir de la misma configuración inicial, aceptando una cadena si alguna rama del árbol la acepta. Sin embargo, es posible simular NTM con DTM, y de hecho, esto puede hacerse de varias maneras.

Multiplicidad de estados de configuración

Un enfoque consiste en utilizar una DTM cuyas configuraciones representen múltiples configuraciones de la NTM, y el funcionamiento de la DTM consiste en visitar cada una de ellas sucesivamente, ejecutar un único paso en cada visita y generar nuevas configuraciones siempre que la relación de transición defina múltiples continuaciones.

Multiplicidad de cintas

Otra construcción simula las NTM con DTM de 3 cintas, en las que la primera cinta siempre contiene la cadena de entrada original, la segunda se utiliza para simular un cálculo particular de la NTM y la tercera codifica una ruta en el árbol de cálculo de la NTM. [ 3 ] Las DTM de 3 cintas se simulan fácilmente con una DTM normal de una sola cinta.

Complejidad temporal y P frente a NP

En la construcción de multiplicidad de cintas , la DTM construida realiza una búsqueda en anchura del árbol de computación de la NTM, visitando todas las posibles computaciones de la NTM en orden de longitud creciente hasta encontrar una que la acepte. Por lo tanto, la longitud de una computación que acepta la DTM es, en general, exponencial con respecto a la longitud de la computación que acepta la NTM más corta. Se cree que esta es una propiedad general de las simulaciones de NTM mediante DTM. El problema P versus NP , la cuestión sin resolver más famosa en informática, se refiere a un caso de este problema: si todo problema resoluble por una NTM en tiempo polinomial es necesariamente también resoluble por una DTM en tiempo polinomial.

No determinismo limitado

Una NTM posee la propiedad de no determinismo limitado. Es decir, si una NTM siempre se detiene en una cinta de entrada T dada , entonces se detiene en un número limitado de pasos y, por lo tanto, solo puede tener un número limitado de configuraciones posibles.

Comparación con las computadoras cuánticas

La forma sospechada del rango de problemas resolubles por computadoras cuánticas en tiempo polinomial (BQP). Nótese que la figura sugierePAG≠nortePAG{\displaystyle {\mathsf {P}}\neq {\mathsf {NP}}}ynortePAG≠PAGSPAGAdomi{\displaystyle {\mathsf {NP}}\neq {\mathsf {PSPACE}}}Si esto no es cierto, entonces la figura debería verse diferente.

Debido a que las computadoras cuánticas usan bits cuánticos , que pueden estar en superposiciones de estados, en lugar de bits convencionales, a veces existe la idea errónea de que las computadoras cuánticas son máquinas de Turing no lineales (MTN). [ 4 ] Sin embargo, los expertos creen (aunque no se ha demostrado) que la potencia de las computadoras cuánticas es, de hecho, incomparable con la de las MTN; es decir, es probable que existan problemas que una MTN podría resolver eficientemente pero que una computadora cuántica no puede, y viceversa. [ 5 ] En particular, es probable que los problemas NP-completos sean resolubles por las MTN pero no por las computadoras cuánticas en tiempo polinomial.

Intuitivamente hablando, si bien una computadora cuántica puede encontrarse en un estado de superposición que corresponde a la ejecución simultánea de todas las ramas computacionales posibles (similar a una máquina de Turing no lineal), la medición final la reducirá a una rama seleccionada aleatoriamente. Esta rama, por lo general, no representa la solución buscada, a diferencia de la máquina de Turing no lineal, que puede elegir la solución correcta entre un número exponencial de ramas.

Véase también

Referencias

  1. ↑ Garey, Michael R.; David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness . WH Freeman. ISBN 0-7167-1045-5.
  2. ↑ Erickson, Jeff. "Máquinas de Turing no deterministas" (PDF) . U. Illinois Urbana-Champaign . Consultado el 7 de abril de 2019 .
  3. ↑ Lewis, Harry R.; Papadimitriou , Christos (1981). «Sección 4.6: Máquinas de Turing no deterministas». Elementos de la teoría de la computación (1.ª ed.). Englewood Cliffs, Nueva Jersey: Prentice-Hall. págs. 204-211 . ISBN   978-0132624787.
  4. ↑ Preguntas frecuentes sobre la computadora cuántica Orion y su desinformación , Scott Aaronson .
  5. ^ Tušarová, Teresa (2004). "Clases de complejidad cuántica". arXiv : cs/0409051 ..

General

  • Martin, John C. (1997). «Sección 9.6: Máquinas de Turing no deterministas». Introducción a los lenguajes y la teoría de la computación (2.ª  ed.). McGraw-Hill. págs. 277–281 . ISBN  978-0073191461.
  • Papadimitriou, Christos (1993). «Sección 2.7: Máquinas no deterministas». Complejidad computacional (1.ª  ed.). Addison-Wesley. pp. 45–50 . ISBN  978-0201530827.
  • Simulador en C++ de una máquina de Turing multitapa no determinista (software libre).
  • Enlace de descarga del simulador C++ de una máquina de Turing multitape no determinista desde sourceforge.net