Máquina de Turing no determinista
En la informática teórica , una máquina de Turing no determinista ( NTM ) es un modelo teórico de cálculo cuyas reglas de gobierno especifican más de una acción posible en determinadas situaciones. Es decir, el siguiente estado de una NTM no está completamente determinado por su acción y el símbolo actual que ve, a diferencia de una máquina de Turing determinista .
Las MNA se utilizan a veces en experimentos mentales para examinar las capacidades y los límites 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 cuestión de cuán difícil es simular un cálculo no determinista con una computadora determinista.
En esencia, se imagina que una máquina de Turing es una computadora simple que lee y escribe símbolos uno a la vez en una cinta sin fin siguiendo estrictamente un conjunto de reglas. Determina qué acción debe realizar a continuación de acuerdo con su estado interno y qué símbolo ve actualmente . 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 cambia al estado 3."
En una máquina de Turing determinista (DTM), el conjunto de reglas prescribe como máximo una acción a realizar para cualquier situación dada.
Una máquina de Turing determinista tiene una función de transición que, para un estado y símbolo dados debajo del cabezal de la cinta, especifica tres cosas:
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 hacia la derecha y cambie al estado 5.
