AL5. Computabilidad Básica. (6 horas)

Tópicos

• Máquinas de estado finito.
• Gramáticas libres del contexto.
• Problemas tratables e intratables.
• Funciones no computables.
• El problema de la parada.
• Implicaciones de la no-computabilidad.

Objetivos

• Discutir el concepto de máquinas de estado finito.
• Explicar las gramáticas libres de contexto.
• Diseñar una máquina de estados finitos determinística para aceptar un lenguage específico.
• Explicar cómo algunos problemas no tienen solución algorítmica.
• Proveer ejemplos que ilustren el concepto de no-computabilidad.