Unidad 6: MT

Question 1

Una MT es un ALA cuya cinta es infinita (cadena mas blancos)

Definición formal de la máquina de Turing

Answer 1

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

Question 2

Qué lenguaje reconoce las MT?

Answer 2

Tipo 0: lenguajes sin restricciones

Question 3

Funcionamiento de la MT

Answer 3

1. Lee un símbolo de entrada
2. Graba un símbolo de salida
3. Transita a un estado
4. Mueve el cabezal (I, D, N, P)
5. Repite 1,2,3,4 hasta ejecutar una instrucción de Parada
6. Se detiene y acepta o rechaza la cadena de entrada

Question 4

Consideraciones del funcionamiento de la MT

Answer 4

• 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

Question 5

Configuración instantánea de la MT

Answer 5

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 < -∞

Question 6

Configuración inicial y final

Answer 6

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.

Question 7

Reconocimiento de cadenas

Answer 7

1. Una MT acepta una cadena de símbolos de entrada si puede detenerse en un estado de aceptación
2. 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

Question 8

Movimiento del MT

Cambio de una configuración a otra

Answer 8

(qt , ƀαtƀ, nt ) Ͱ (qt +1 , ƀαt +1 ƀ, nt+1)

Question 9

Movimiento generalizado

Cambio de configuración inicial a final

Answer 9

(qt , ƀαtƀ, nt ) Ͱ* (qt +k , ƀαt +k ƀ, nt+k)

Question 10

Variantes de MT

MT Modular

Answer 10

• 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

Question 11

Variantes de MT

MT Universal

Answer 11

• 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

Question 12

Varienates de MT

MT Generalizada

Answer 12

• Incorpora más Hardware a su versión original
• Tiene un número arbitrario de cintas y puede tener múltiples cabezales

Question 13

Variantes de MT

MTND

Answer 13

• 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

Question 14

Complejidad

Tipos de complejidad

Answer 14

1. LÓGICA: mide la sencillez de ña solución
2. DE RECURSOS: mide cuantos recursos insume la ejecución de la solución

Question 15

Complejidad

Complejidad de Shannon

Answer 15

• Mide la complejidad de una MT según la cantidad de conecciones en el grafo
• Complejidad = |Q| × |Γ|

Question 16

Teoremas de complejidad (Shannon)

Teorema 1

Answer 16

Cualquier MT con |Γ|=m y |Q|=n puede ser simulada por otra MT’ con solo 2 estados y 4.m.n+m símbolos

Question 17

Teoremas de complejidad (Shannon)

Teorema 2

Answer 17

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

Question 18

Complejidad

Complejidad temporal

Answer 18

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

Question 19

Complejidad

Complejidad espacial

Answer 19

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.

Question 20

Clases de problemas

Answer 20

• 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