Cours : Natacha Portier (Natacha.Portier)
TD : Ivan Morel, Irénée Briquel (Ivan.Morel, Irenee.Briquel)
Ce cours comportera une partie calculabilité et une partie logique, d’importances équivalentes. La partie calculabilité est centrée autour de la notion de machine de Turing (définitions, exemples machines de Turing universelles, thèse de Church, problème de l’arrêt, ensembles récursivement énumérables...). Dans la partie logique, on étudie la notion d’énoncé, de preuve et de modèle, et plus précisément le calcul propositionnel et le calcul des prédicats. Le point d’orgue de ce cours est la démonstration du théorème d’incomplétude de Gödel.