Tipos de MAQUINA 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, lasacciones a tomar en función de una entrada. En el caso de que para cada par (estado, símbolo) posible exista a losumo una posibilidad de ejecución, se dirá que es una máquina de Turing determinista, mientras que en el caso deque exista al menos un par (estado, símbolo) con más de una posible combinación de actuaciones se dirá que setrata 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 quefinalmente 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 unamáquina determinista sigue un único "camino computacional", una máquina no determinista tiene un "árbolmáquina determinista sigue un único "camino computacional", una máquina no determinista tiene un "árbolcomputacional". Si cualquiera de las ramas del árbol finaliza en un estado de aceptación, se dice que la máquinaacepta la entrada.

La capacidad de cómputo de ambas versiones es equivalente; se puede demostrar que dada unamáquina de Turing no determinista existe otra máquina de Turing determinista equivalente, en el sentido de quereconoce el mismo lenguaje, y viceversa. No obstante, la velocidad de ejecución de ambos formalismos no es lamisma, pues si una máquina no determinista M reconoce una cierta palabra de tamaño n en un tiempo , la máquinadeterminista equivalente reconocerá la palabra en un tiempo . Es decir, el no determinismo permitirá reducir lacomplejidad de la solución de los problemas, permitiendo resolver, por ejemplo, problemas de complejidadexponencial en un tiempo polinómico.