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 
CARACTERISTICAS DE LA MAQUINA DE TURING DETERMINISTA
1-Cinta infinita: La cinta se divide en casillas, y cada casilla puede contener un símbolo de un conjunto finito de símbolos.
2-Cabeza de lectura/escritura: La cabeza puede
leer el símbolo en la casilla actual, escribir un nuevo símbolo en esa casilla
y moverse a la izquierda o a la derecha a lo largo de la cinta.
3-Conjunto finito de estados: La máquina tiene
un conjunto finito de estados, y en cada paso, la máquina está en un estado
particular.
4-Función de transición: Hay una función de transición que determina cómo la máquina cambia de estado en respuesta al símbolo leído y a su estado actual.
¿CÓMO SABE UNA MAQUINA NO DETERMINISTA QUE 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 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.
1-En una máquina de
Turing no determinista, en cambio, en un dado estado y símbolo de entrada,
hay múltiples transiciones posibles.
2-La máquina puede
estar en varios estados al mismo tiempo y explorar múltiples ramas de cómputo
simultáneamente.
3-Estas máquinas no
deterministas son más expresivas en términos de capacidad computacional, ya que
pueden representar de manera más eficiente ciertos problemas que las máquinas
deterministas.
4-En términos prácticos, las máquinas de Turing deterministas son más fáciles de entender y simular, pero las máquinas de Turing no deterministas son útiles en la teoría de la complejidad computacional para describir ciertos algoritmos y problemas de manera más concisa.
5-Ambos tipos de máquinas son modelos abstractos y teóricos que ayudan a los científicos de la computación a comprender y analizar la naturaleza de los algoritmos y la computación.
No hay comentarios.:
Publicar un comentario