Tipos de Máquina de Turing

Máquina de Turing Determinista y No Determinista

La entrada de una máquina de Turing viene determinada por el estado actual y el

símbolo leído, un par (estado, símbolo), siendo el cambio de estado, la escritura de un

nuevo símbolo y el movimiento del cabezal, las acciones a tomar en función de una

entrada. En el caso de que para cada par (estado, símbolo) posible exista a lo sumo una

posibilidad de ejecución, se dirá que es una máquina de Turing determinista, mientras que

en el caso de que exista al menos un par (estado, símbolo) con más de una posible

combinación de actuaciones se dirá que se trata de una máquina de Turing no determinista.

La función de transición en el caso no determinista, queda definida como sigue:

¿Cómo sabe una máquina no determinista qué acción tomar de las varias posibles?

Hay dos formas de verlo: una es decir que la máquina es "el mejor adivino posible", esto es,

que siempre elige la transición que finalmente la llevará a un estado final de aceptación. La

otra es imaginarse que la máquina se "clona", bifurcándose en varias copias, cada una de

las cuales sigue una de las posibles transiciones. Mientras que una máquina determinista

sigue un único "camino computacional", una máquina no determinista tiene un "árbol

computacional". Si cualquiera de las ramas del árbol finaliza en un estado de aceptación, se

dice que la máquina acepta la entrada.

La capacidad de cómputo de ambas versiones es equivalente; se puede demostrar

que dada una máquina de Turing no determinista existe otra máquina de Turing

determinista equivalente, en el sentido de que reconoce el mismo lenguaje, y viceversa. No

obstante, la velocidad de ejecución de ambos formalismos no es la misma, pues si una

máquina no determinista M reconoce una cierta palabra de tamaño n en un

tiempo , la máquina determinista equivalente reconocerá la palabra

en un tiempo . Es decir, el no determinismo permitirá reducir la

complejidad de la solución de los problemas, permitiendo resolver, por ejemplo, problemas

de complejidad exponencial en un tiempo polinómico