Fonctions Récursives

UMH-?? -- Christian Michaux -- 15-0-0 -- Cours de 2ème cycle

Objectif

Introduction des concepts de base de la théorie des fonctions récursives, application à des problèmes de décidabilité

Prérequis

avoir suivi un cours élémentaire d'informatique

Contenu

Nous introduisons les concepts de base de la théorie des fonctions récursives via l'axiomatique due à Shoenfield. Nous démontrons l'indécidabilité du ``Halting Problem''. Dans la seconde partie, nous étudions une application (par exemple le 10ème Problème d'Hilbert).

Pédagogie

Examen oral (45 min) dont une partie concerne un travail à préparer (libre choix, par exemple: détailler une partie non traitée de l'application, exposer une autre application, ...)

Références

25
N.J. Cutland, Computability : An introduction to recursive function theory, Cambridge University Press, Cambridge, 1980.

26
J.R. Shoenfield, Degrees of Unsolvability, North Holland, NY, 1971.