Maquinas De Turing

Universidad de Oriente.
Núcleo Anzoátegui.
Escuela de Ingeniería y Ciencias Aplicadas.
Departamento de Computación y Sistemas.
Ingeniería en Computación.
Teoría de los Autómatas y Lenguajes Formales.
Sección 01.


Máquinas
de Turing

1. Defina formalmente una Máquina de Turing.
Una máquina de Turing con una sola cinta puede ser definida como una 7-tupla M=(Q, ∑, s, b, Γ, δ),donde:
• 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.(∑ Є Γ)
• s Є Q es el estado inicial.
• b Є Γ es un símbolo denominado blanco, y es el único símbolo que se puede repetir un número infinito de veces.
• esel conjunto de estados finales de aceptación.
• δ : Q × Γ → Q × Γ { L, R} es una función parcial denominada función de transición, donde L es un movimiento a la izquierda y R es el movimiento a la derecha.
2. Las Máquinas de Turing No deterministas y Deterministas, tienen el mismo poder de reconocimiento?
La entrada de una máquina de Turing viene determinada por el estado actual y el símbololeído, un par [estado, símbolo], siendo el cambio de estado, la escritura de un nuevo símbolo y el movimiento las acciones a tomar en función de una entrada. En el caso de que para cada par estado y 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 unaposible 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: δ : Q × Γ → P(Q × Γ × {L, R}
¿Cómo sabe una máquina no determinista cuál de las varias actuaciones tomar? Hay dos formas de verlo: una es decir que la máquina es "el mejor adivino posible", esto es, que siempre eligela transición que eventualmente 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 solo "camino computacional", una máquina no determinista tiene un "árbol computacional". Si cualquiera de las ramas del árbolfinaliza 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 siuna máquina no determinista M reconoce una cierta palabra de tamaño n en un tiempo O(t(n)), la máquina determinista equivalente reconocerá la palabra en un tiempo O(2t(n)). 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.
3. Cuál es la diferencia entre unalgoritmo y un proceso computacional, según la teoría de autómatas?
Para responder esta pregunta primero debo decir que “… al ejecutarse un programa, se lleva a cabo un proceso computacional”. Entonces de aquí llego a la conclusión que el algoritmo se refiere a la secuencia de pasos para resolver un problema independientemente del lenguaje que de utilice, mientras que en un proceso computacionalse refiere propiamente a la codificación de un algoritmo en algún lenguaje de programación.
4. Que es un orden de algoritmo?
El orden de algoritmo indica el grado de complejidad de un algoritmo y que sirve de base para comparar su eficiencia.
5. Que es un problema P?
Para responder esta pregunta y la que viene es necesario saber el concepto de problema de decisión; el cual es un problema...