Le cours décrit trois grands modèles de calcul que sont les machines de Turing, les fonctions récursives et enfin les lambda-calculs.
On s'intéresse d'abord à l'aspect très opérationnel, syntaxique et impératif des machines de Turing. Ce modèle permet de définir des notions de calculabilité : ce qu'il est possible de faire, et de complexité : à quel coût ? Le cours aborde ensuite la description algébrique du comportement des fonctions avec les fonctions récursives de Gödel. La troisième partie est enfin consacrée aux lambda-calculs et aux familles de langages de programmation qui en descendent. Ces trois modèles sont montrés équivalents du point de vue de l'expressivité : bien que très différents, ils décrivent le même ensemble de programmes.
L'un des objectifs est d'acquérir une compréhension de l'objet à programmer et donc indépendance et adaptabilité vis-à-vis des langages disponibles. C'est au travers de la notion de réduction que sont perçus les coûts et contraintes entraînés par l'utilisation de bibliothèques ou solutions externes pour résoudre un problème.
- Machines de Turing, simplifications
- Problèmes de décision, réductions
- Complexité, classes P et NP, complétude
- Fonctions récursives
- Lambda-calcul pur, lambda-calculs typés
