Unidad 6: MT Flashcards
Una MT es un ALA cuya cinta es infinita (cadena mas blancos)
Definición formal de la máquina de Turing
MT = ( Σ, Γ, Q, q0 , A, f , ƀ )
cuyos componentes son:
- Σ = alfabeto de símbolos de entrada
- Γ = Σ ∪ {ƀ} ∪ Ω = alfabeto de símbolos de cinta – ƀ=blanco
- Q = conjunto finito y no vacío de estados posibles
- q0∈Q = estado inicial de funcionamiento
- A⊆Q = conjunto de estados de aceptación
- f : Q x Γ → Q x Γ x {I, D, N, P} = función de transición
Qué lenguaje reconoce las MT?
Tipo 0: lenguajes sin restricciones
Funcionamiento de la MT
- Lee un símbolo de entrada
- Graba un símbolo de salida
- Transita a un estado
- Mueve el cabezal (I, D, N, P)
- Repite 1,2,3,4 hasta ejecutar una instrucción de Parada
- Se detiene y acepta o rechaza la cadena de entrada
Consideraciones del funcionamiento de la MT
- Puede modificar las celdas de la cinta
- Puede quedar atrapada en un ciclo infinito y no terminar
- Puede aceptar una cadena sin leerela completamente con detenerse en un estado de aceptación
Configuración instantánea de la MT
Kt = (qt, ƀαtƀ, n)
qt ∈ Q → estado actual en el instante t
α t ∈ Γ ∗ → contenido de la cinta en el instante t
n ∈ N →: posición del cabezal sobre la cinta, -∞ < n < -∞
Configuración inicial y final
Configuración inicial: K0 = (q0 , ƀα0ƀ, 1)
Configuración final: Kn = (qn , ƀαn ƀ, m) con MT detenida.
Si qn∈A, ésta ES una configuración de aceptación.
Reconocimiento de cadenas
- Una MT acepta una cadena de símbolos de entrada si puede detenerse en un estado de aceptación
- Una MT acepta una cadena de símbolos de entrada si puede moverse desde una configuración inicial a una configuración final de aceptación y detenerse.
(q0 , ƀ α ƀ, 0) Ͱ* (qf , ƀ β ƀ, m) con qf∈A
Movimiento del MT
Cambio de una configuración a otra
(qt , ƀαtƀ, nt ) Ͱ (qt +1 , ƀαt +1 ƀ, nt+1)
Movimiento generalizado
Cambio de configuración inicial a final
(qt , ƀαtƀ, nt ) Ͱ* (qt +k , ƀαt +k ƀ, nt+k)
Variantes de MT
MT Modular
- Construcción de autómatas mayores a partir de aislar y asignar sus funciones principales a máquinas individuales, que luego se incorporan a la principal
- Pequeñas MT que realizan funciones sencillas para combinarlas con otras. Resuelven problemas complejos de forma sencilla
Variantes de MT
MT Universal
- Recibe en su cinta otra MT y produce como resultado de su ejecución el mismo resultado de la MT de la cinta
- Es capaz de simular el comportamiento de cualquier MT
Varienates de MT
MT Generalizada
- Incorpora más Hardware a su versión original
- Tiene un número arbitrario de cintas y puede tener múltiples cabezales
Variantes de MT
MTND
- función f : Q x Γ → P (Q x Γ x {I, D, N, P})
- Puede hacer en cada paso varias cosas distintas en simultáneo
- Siempre tiene un MTD con una sola cinta equivalente
Complejidad
Tipos de complejidad
- LÓGICA: mide la sencillez de ña solución
- DE RECURSOS: mide cuantos recursos insume la ejecución de la solución
Complejidad
Complejidad de Shannon
- Mide la complejidad de una MT según la cantidad de conecciones en el grafo
- Complejidad = |Q| × |Γ|
Teoremas de complejidad (Shannon)
Teorema 1
Cualquier MT con |Γ|=m y |Q|=n puede ser simulada por otra MT’ con solo 2 estados y 4.m.n+m símbolos
Teoremas de complejidad (Shannon)
Teorema 2
Cualquier MT con |Γ|=m y |Q|=n puede ser simulada por una MT’ con sólo dos símbolos y
menos de 8.m.n estados
Complejidad
Complejidad temporal
Es una función T(n) que determina la cantidad de movimientos (o unidades elementales de tiempo) que utiliza en resolver un problema con datos de entrada α de largo |α|=n
Complejidad
Complejidad espacial
Es la función E(n) que determina la cantidad de celdas en cinta (memoria) que usa para resolver un problema con datos de entrada α de largo |α|=n.
Clases de problemas
- Clase P: problemas que pueden resolverse con una MT determinista en un tiempo polinómico o menor
- Clase NP: problemas que pueden resolverse con una MT no determinista en tiempo polinómico o menor
- CLase NP-Completos: subproblemas de la clase NP a los que cualquier otro problema de NP puede reducirse en tiempo polinómico
