Presentación del grupo 4395 - 2009-1.

PROFESORES: PAULO MAXIMO GUTIERREZ GONZALEZ Y ROBERTO CALDERON JUAREZ

MOTIVACION:

A través de los siglos los matemáticos han tenido éxito en descubrir o inventar nuevos algoritmos. Por tanto, y de forma natural, se dio origen a la cuestión de si, con el esfuerzo suficiente, llegaría el momento en que cada grupo de problemas pudiera ser atacado por un procedimiento general.Con la no decidibilidad de la lógica de primer orden (que se demuestra directamente de la no decidibilidad del“Halting problem“ en máquinas de Turing), se vino abajo tal cuestión, quedando de manifiesto la no computabilidd de un número importante de problemas.

INTRODUCCION

Se introduce la noción de computabilidad por medio de máquinas de Turing; y se introduce también la noción de μ-recursividad que es otra caracterización equivalente a máquinas de Turing.

TEMARIO:

MAQUINAS DE TURING

Definición de Máquina de Turing

Combinación de Máquinas de Turing

Máquinas de Turing Especiales

Ejemplos de Computabilidad y Decidibilidad Según Turing

FUNCIONES μ-RECURSIVAS

Funciones Primitivas Recursivas

Predicados Primitivos Recursivos

El Operador μ

Ejemplos de Funciones Computables que no son Primitivas Recursivas

Funciones y Predicados μ-Recursivos

EQUIVALENCIA DE TURING-COMPUTABLE Y μ-RECURSIVO

Computabilidad Según Turing

La Turing-Computabilidad de Funciones μ-Recursivas

Numeración de Gödel de Máquinas de Turing

La μ-Recursividad de Funciones Turing-Computables.

Forma Normal de Kleene

FUNCIONES RECURSIVAS

Definición de Funciones Recursivas

La Recursividad de las Funciones μ-Recursivas

La μ-Recursividad de las Funciones Recursivas

BIBLIOGRAFIA BASICA

Davis, Martin, Computability and Unsolvability, McGraw-Hill, 1958.

Hermes, H., Enumerability, Decidability, Computability, Springer-Verlag, 1969.

George S. Boolos; Richard C. Jeffrey, Computability and Logic, CambridgeUniversity Press, 1989.

FORMA DE EVALUACION

Tres o cuatro exámenes parciales80%

Participación en clase10%

Tareas10%