IFT631 - Calculabilité et décidabilité
Présentation
Sommaire
- Cycle
- 1er cycle
- Crédits
- 3 crédits
- Faculté ou centre
- Faculté des sciences
Cible(s) de formation
S'initier aux principales questions soulevées par la théorie de la calculabilité, en particulier par l'étude de problèmes décidables et indécidables; étudier les liens qui existent entre les concepts destinés à formaliser le concept de calculabilité effective.
Contenu
Machines de Turing, indécidabilité. Thèse de Church. Relativisation et niveaux d'indécidabilité. Fonctions récursives et théorème de Turing. Logique propositionnelle et théories logiques du premier ordre. Complétude et décidabilité du calcul propositionnel, théorèmes de Gödel.