maquina de turing

1. Defina formalmente una maquina de Turing deterministica.
Una máquina de Turing (MT) es un modelo computacional que realiza una lectura/escritura de manera automática sobre una entrada llamada cinta, generando una salida en esta misma.
Este modelo está formado por un alfabeto de entrada y uno de salida, un símbolo especial llamado blanco (que denota las secciones sin escribir de la cinta),un conjunto de estados finitos y un conjunto de transiciones entre dichos estados. Su funcionamiento se basa en una función de transición, que recibe un estado inicial y una cadena de caracteres (la cinta, la cual puede ser infinita) pertenecientes al alfabeto de entrada. La máquina va leyendo una celda de la cinta en cada paso, borrando el símbolo en el que se encuentra posicionado su cabezal yescribiendo un nuevo símbolo perteneciente al alfabeto de salida, para luego desplazar el cabezal a la izquierda o a la derecha (solo una celda a la vez). Esto se repite según se indique en la función de transición, para finalmente detenerse en un estado final o de aceptación, representando así la salida.
Formalmente, una máquina de Turing con una sola cinta puede definirse como una septuplaDónde:
es un conjunto finito de estados.
es un conjunto finito de símbolos distinto del espacio en blanco, denominado alfabeto de máquina o de entrada.
es un conjunto finito de símbolos de cinta, denominado alfabeto de cinta .
es el estado inicial.
es un símbolo denominado blanco, y es el único símbolo que se puede repetir un número infinito de veces.
es el conjunto de estados finales deaceptación.
es una función parcial denominada función de transición, donde es un movimiento a la izquierda y es el movimiento a la derecha.
Existen en la literatura un abundante número de definiciones alternativas, pero todas ellas tienen el mismo poder computacional, por ejemplo se puede añadir el símbolo como símbolo de "no movimiento" en un paso de cómputo.
2. Defina formalmente unaMaquina de Turing no deterministica.
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, sedirá 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 "caminocomputacional", 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 mismolenguaje, 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,...