La théorie de la calculabilité s'intéresse essentiellement à la question suivante : au moyen d'un ordinateur, quelles fonctions peut-on calculer et quels problèmes peut-on résoudre ? Son développement est concomitant de l'apparition des principaux modèles de calcul (fonctions récursives, machines de Turing, lambda-calcul,...) et est très étroitement lié à la logique mathématique : théorème d'incomplétude de Gödel (qui sera abordé dans ce cours), lambda-calcul typé (cours Preuves et types)...
La complexité cherche quant à elle à mesurer le degré de difficulté d'un problème, typiquement en termes de temps de calcul et d'espace utilisé. Il s'agit donc de questions plus fines, qui font l'objet de nombreuses recherches actuelles, notamment en rapport avec la logique.
L'objectif de ce cours est de présenter les outils et résultats fondamentaux pour aborder ces questions.
Programme :
- Fonctions récursives, théorème de Kleene.
- Machines de Turing, thèse de Church.
- Arithmétique de Peano, théorème de Gödel.
- Quelques méthodes et théorèmes de base en théorie de la complexité.
