Lenguajes Formales y Computabilidad

Gramáticas regulares y libres de contexto. Autómatas a pila y lenguajes libres de contexto. Máquinas de Turing. Funciones recursivas. Funciones parcialmente computables. Tesis de Church. El halting problem. Programas universales. Teoremas del parámetro, de la recursión y de Rice. Forma normal de Kleene de una función parcialmente computable. Conjuntos r.e. Lenguajes r.e. Funciones parcialmente computables sobre palabras. Equivalencia entre las funciones recursivas parciales, funciones Turing computables y funciones parcialmente computables. Relación entre los distintos formalismos de cómputo.