Cours fondamental : Calculabilité et incomplétude.

Systèmes de déduction, fonctions récursives, fonctions calculables par machine. Théorèmes d'indécidabilité. Théorèmes d'incomplétude de Gödel. Classes de complexité (P, NP), problèmes NP-complets.

Année 2005-2006

• Semaine 1 : systèmes de déduction, introduction à la déduction naturelle, équivalence avec un système à la Hilbert polycopié + exercices.
.
• Semaine 2 : fonctions primitives récursives, le cours est repris sous forme d'exercices dans la feuille 1.
  • Feuille d'exercices 1: exemples de fonctions primitives récursives, schémas de clôture.
  • Feuille d'exercices 2: fonctions élémentaires au sens de Kalmar (non distribuée, dernière partie reprise dans le problème 1).
  • Problème 1 à rendre pour le jeudi 20 octobre.
• Semaine 3 : fonctions récursives partielles (définition dans la feuille 4), machines à registre
  • Feuille d'exercices 3 : fonction d'Ackermann.
  • Feuille d'exercices 4 : fonctions récursives partielles.
• Semaine 4 : équivalence entre fonction calculable par machine à registre et fonction récursive ; forme normale de Kleene, théorème d'énumération, théorème smn.
  • polycopié sur les machines à registres (cours des semaines 3 et 4)
• Semaine 5 : indécidabilité du problème de l'arrêt, ensembles récursivement énumérables, réduction récursive, ensembles complets, théorème du point fixe de Kleene.
  • Feuille d'exercices 5 : fonctions récursives partielles (2).
  • Feuille d'exercices 6 : fonctions récursives partielles (3).
  • Corrigé de la feuille 2 (contient page 7 le corrigé de la seconde partie du problème 1).
  • Corrigé du problème 1.
  Problème 2 à rendre pour le jeudi 10 novembre.
• Semaine 6 : pas de séance le mardi 1/11/05 ; deuxième et troisième théorème de point fixe. Applications du théorème s-m-n et des théorèmes de point fixe : la fonction d'Ackermann est récursive, le lemme de "rembourrage" démontré sans référence aux machines ... Axiomatisation des familles de fonctions universelles pour les fonctions récursives, équivalence par fonctions récursives (équivalence par injections récursives, et bijection récursive esquissée).
• Semaine 7 : sous-ensembles extensionnels (au sens ensembliste) récursivement énumérables de N : la classe d'ensemble associée est stable par inclusion, tout ensemble de la classe contient un sous-ensemble fini qui est dans la classe (Rice-Shapiro).
  Caractérisation des fonctions récursives sans récurrence, ensembles Sigma, les ensembles récursivement énumérables sont Sigma, hiérarchie arithmétique.
  • Feuille d'exercices 7 : Hiérarchie arithmétique, reprend les résultats de base sur la hiérarchie arithmétique.
• Semaine 8 : partiels les mardi 15/11/05 matin (R. Cori) et jeudi 17/11/05 matin (P. Rozière).
  Hiérarchie arithmétique. Théories arithmétiques : théories R-, R, R+ de Robinson, Sigma-complétude.
  ¾
  • corrigé exercice 13, feuille 6
  • Énoncé du partiel
• Semaine 9 : arithmétique finie de Robinson, arithmétique de Peano ; arithmétisation de la syntaxe ; cohérence et Sigma-cohérence ; premier théorème d'incomplétude de Gödel.
• Semaine 10 : mardi 29 novembre -- ensemble faiblement représentable, ensemble représentable dans une théorie. Théorème de Gödel-Rosser. Indécidabilité des théories arithmétiques, indécidabilité du calcul des prédicats pur. 2nd théorème d'incomplétude de Gödel. A partir du jeudi 1er décembre et les deux semaines suivantes le cours de complexité est assuré par Richard Lassaigne.
  • Corrigé du partiel
  • Feuille d'exercices 8 : Théorèmes de Gödel et Gödel-Rosser, représentabilité ...
• examen le mercredi 4 janvier 2005 de 9h à 12h en salle 0D9.
  • énoncé
  • corrigé

Références.

• R. Cori, D. Lascar : Logique mathématique : cours et exercices (tome 2, Masson, 1993)
• C. Smorynski : Logical Number Theory I : an Introduction (Springer Verlag, 1991)
• P. Oddifredi : Classical recursion theory (North Holland, 1989)
• H. Rogers : Theory of recursive functions and effective computability (Mc Graw-Hill, 1967)
• S.C. Kleene : Introduction to metamathematics (North Holland, 1952).