On décrit les modèles les plus généraux de calcul et de décision en informatique (qui sont équivalents) : machine de Turing, grammaire, fonction mu-récursive (avec cas particulier des fonctions récursives primitives).
On précise la signification du non-déterminisme dans le calcul et la décision.
Ensuite on donne les limites de ces modèles en montrant l'impossibilité de décider généralement certaines questions, comme l'arrêt d'une machine de Turing.
Enfin on donne les classes fondamentales de complexité des algorithmes, P, NP et EXP, en particulier les problèmes NP-complets.

À l'issue de cette UE, un étudiant saura :
- Faire preuve d'esprit critique face à des « solutions » trop générales ;
- Comprendre l'équivalence des divers langages informatiques avec la machine de Turing ;
- Connaître les limites de l'informatique ;
- Maîtriser le non-déterminisme ;
- Être capable de classer des problèmes informatiques en : faisables en pratique ; possibles en principe mais infaisables en pratique ; impossibles en principe.

P. Wolper, Introduction à la calculabilité : Cours et exercices corrigés, Edition Dunod
J.-F. Rey, Calculabilité, complexité et approximation, Edition Vuibert

Théorie des langages