Calculabilité

CalculabilitéCode de l'UE : HMIN221M

Présentation

La théorie de la calculabilité tourne autour de deux notions phares : les modèles de calcul et les réductions entre problèmes. Le cours commence par une présentation et des rappels sur différents modèles de calcul ayant diverses puissances de calcul, allant des automates finis aux machines de Turing en passant par la récursion primitive. Nous étudions alors différentes notions de réductions d'un problème à un autre pour ensuite présenter différents ensembles canoniques et les théorèmes principaux de la calculabilité naïve, tels l'ensemble diagonal, les ensembles d'indices de fonctions, les théorèmes de point-fixe de Kleene, le théorème de Rice, l'isomorphisme de Rogers, etc. Le cours se termine par un aperçu de la structure induite par les réductions sur les ensembles d'entiers quelconques et les ensembles récursivement énumérables. En particulier nous construisons différentes solutions au problème de Post.

Volume horaire

  • CM : 16.5
  • TD : 33
  • TP : 0
Diplômes intégrant cette UE

En bref

Crédits ECTS 5

Période de l'année
secondSemestre

Contact(s)

Contact(s) administratif(s)

Bruno DURAND (bruno.durand @ umontpellier.fr)