Máquina de Turing - Cuadro comparativo

Vista previa del material en texto

Instituto Tecnológico Superior 
Progreso 
Dirección General 
Subdirección Académica 
 
 
 
Boulevard Tecnológico de Progreso S/N por 62, Progreso, Yucatán. C.P. 97320 
Tels. 969 934 3023, tecnm.mx | progreso.tecnm.mx 
 
 
 
 
 
 
 
 
 
 Instituto Tecnológico Superior Progreso 
 
CARRERA: 
Ingeniería en Sistemas Computacionales 
 
MATERIA: 
Lenguajes y Autómatas I 
 
TAREA: 
Máquina de Turing - Cuadro comparativo 
 
MAESTRO: 
DR. MARTÍNEZ GARCÍA HOLZEN ATOCHA 
 
ESTUDIANTE: 
Miguel Angel De La Cruz Centeno 
 
SEMESTRE: 
6to SEMESTRE 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Instituto Tecnológico Superior 
Progreso 
Dirección General 
Subdirección Académica 
 
 
 
Boulevard Tecnológico de Progreso S/N por 62, Progreso, Yucatán. C.P. 97320 
Tels. 969 934 3023, tecnm.mx | progreso.tecnm.mx 
 
 
 
Característica 
Máquina de 
Turing 
Determinista 
(MTD) 
Máquina de 
Turing No 
Determinista 
(MTND) 
Máquina de 
Turing 
Oráculo (MTO) 
Máquina de 
Turing 
Multicinta 
(MTM) 
Determinismo SI NO SI SI 
Conjunto de 
estados 
Finito Finito Finito Finito 
Transiciones Deterministas No 
Deterministas 
Deterministas Deterministas 
Cinta Una cinta Una cinta Una cinta Múltiples cintas 
Expresividad Limitada Mayor 
expresividad 
Mayor 
expresividad 
Mayor 
expresividad 
Complejidad 
computacional 
Menos potente 
que MTND y 
MTM 
Más potente 
que MTD y 
MTM 
Depende del 
oráculo 
Más potente 
que MTD y 
MTND 
Capacidad de 
resolución 
Limitada Mayor 
capacidad de 
resolución 
Depende del 
oráculo 
Mayor 
capacidad de 
resolución