Cours fondamental 2 LMFI : Calculabilité et incomplétude

Année 2021-22

Horaires

• Mardi 16h30-18h30, salle 1020 bâtiment Sophie Germain, à partir du 5/10 16h15-17h15
• Jeudi 13h45-15h45, salle 2013 bâtiment Sophie Germain
• Jeudi 9h00-13h00, salle 2013 bâtiment Sophie Germain (en alternance avec la théorie des modèles et la complexité)

Contenu

• Semaine 1 (14/09/2021) :
  • Pas de cours le mardi 14/09, premier cours le jeudi 16/09.
  • Fonctions récursives primitives ; exemples, schémas de clôture.
  • feuille 1 (révisions du cours ou exercices extraits du polycopié pour la plupart) ; vous pouvez voir d'ici mardi prochain les exercices de 1 à 10 qui sont soit des redites du cours d'aujourd'hui (les faire sans regarder le polycopié), soit des applications directes. Corrigé partiel.
  • Polycopié, pages 1 à 8.
• Semaine 2 (21/09/2021) :
  • codage des uples et des listes ; définition par récurrence sur la suite des valeurs ; récurrences mutuelles et récurrence avec substitution ee paramètre (laissées en execices) ; codage et évaluation des fonctions récursives primitives : une telle fonction ne peut être récursive primitive. Fonction d'Ackermann (démonstrations laissées en exercice). Fonctions partielles calculables et schéma de minimisation.
  • Fonctions partielles, et fonctions totales μ-récursives ; machines à registres avec programme goto.
  • TD calculabilité et incomplétude (à faire exercices 12, 14 questions 2 et 3, 15, 16, 17.1 et 18 de la feuille d'exercices) ; corrigés : ex. 14, 15, 18 q 1 à 8 et 9 en partie. Un corrigé sera mis en ligne en fin de semaine prochaine.
  • Polycopié, pages 1 à 24.
• Semaine 3 (28/09/2021) :
  • Machines à registres avec programme structuré ; fonctions calculables par machine à registres ; les fonctions calculables avec programme structuré sont calculables avec programme goto.
  • Les fonctions partielles μ-récursives sont calculables par machines à registres avec programme structuré (la boucle for suffit pour les fonctions récursives primitives) ; codage des machines et du calcul : les fonctions calculables par machine avec programme goto sont partielles μ-récursives (principe de la démonstration, codages.
  • Polycopié (version provisoire), pages 1 à 32 ; voir sur le polycopié les définitions précises des fonctions d'initialisation, de transition et du prédicat d'arrêt, qui permettent de montrer que ces fonctions sont récursives primitives.
  • forme normale de Kleene ; théorème d'énumération (fonctions et machines universelles) ; indice d'une fonction partielle calculable ; lemme de bourrage.
  • Théorème de paramétrisation (s-m-n).
  • feuille d'exercice 2 sur les machines à registres et les machines de Turing (la présentation des machines de Turing est à peu près celle qui sera utilisée en complexité).
• Semaine 4 (5/10/2021) :
  • Ensembles semi-décidables : définition et caractérisations.
  • Ensembles semi-décidables ; clôture par réunion intersection et projection des semi-décidables ; un ensemble semi-décidable de complémentaire semi-décidable est décidable.
  • Problèmes décidables et indécidables ; indécidabilité du problème de l'arrêt ; il n'est pas possible d'énumérer un ensemble d'indices pour toutes les fonctions totales calculables ; il existe des fonctions partielles récursives qui ne peuvent pas être prolongées par une fonction totale récursive ; Théorème de Rice.
  • feuille d'exercice 3 sur les fonctions partielles calculables, compléter par les exercices 14 p. 34 et 16 p. 40 du poly.
  • Polycopié, pages 1 à 46.
  • TD calculabilité et incomplétude : machines de Turing (feuille 2), calculabilité (feuille 3).
  • Théorème du point fixe de Kleene, la fonction d'Ackermann est calculable ; théorème du point fixe avec paramètres.
  • Systèmes d'indices acceptables : une famille de fonctions par arité surjective sur les partielles calculables de cette arité, vérifiant la propriété d'énumération et celle de paramétrisation ; un système d'indices acceptable vérifie les théorèmes de point fixe et le lemme de bourrage ; équivalence par deux fonctions calculables ; équivalence par une bijection calculable.
  • Polycopié, pages 1 à 50.
• Semaine 5 (12/10/2021) :
  • feuille d'exercice 4 (théorème de Rice-Shapiro).
  • Réduction many-one
  • Calculabilité relativement à une fonction, machine à registres avec oracle ; réduction de Turing.
  • Définissabilité dans ℕ ; ensembles Σ₀.
  • Fonction β de Gödel et caractérisation des fonctions totales calculables sans récurrence ; les graphes des fonctions totales calculables sont Σ ; les ensembles Σ sont exactement les ensembles semi-décidables.
  • Hiérarchie arithmétique : définition.
  • Polycopié, pages 1 à 62.
• Semaine 6 (19/10/2021) :
  • Propriétés de clôture des classes de la hiérarchie arithmétique ; les ensembles Σ₁ sont les ensembles semi-décidables, les ensembles Π₁ les co-semi-décidables, et les ensembles Δ₁ les ensembles décidables ; relations d'inclusion.
  • Énumération des sous-ensembles Σ_n, resp. Π_n, de ℕ par un sous-ensemble Σ_n resp. Π_n, de ℕ² ; les inclusions de la hiérarchie arithmétique sont strictes.
  • La classe des sous-ensembles arithmétiques de ℕ (ensembles définissables dans ℕ dans le langage de l'arithmétique du 1er ordre) n'est pas énumérable par un ensemble arithmétique.
  • Chaque ensemble K_n obtenu par diagonalisation pour une énumération de la classe Σ_n de la hiérarchie arithmétique est m-complet pour cette classe, et son complémentaire pour la classe Π_n ; calculabilité relative et réduction de Turing ; K_n est T-complet pour la classe Δ_n+1. la vérité des énoncés de l'arithmétique n'est pas définissable dans l'arithmétique (théorème de Tarski) comme conséquence du fait que la hiérarchie est stricte.
  • Codage des formules : codage des formules comme arbres binaires étiquetés.
  • Deux démonstrations du théorème de Tarski ; une forme faible du premier théorème d'incomplétude : si l'ensemble des codes des théorèmes de T est semi-décidable et si T et a pour modèle N alors il existe un énoncé arithmétique vrai non démontrable dans T.
  • Théorie décidable ; théorie complète ; théorie effectivement (ou récursivement) axiomatisable ; forme faible du premier théorème d'incomplétude : si T est effectivement axiomatisable et a pour modèle N alors il existe un énoncé arithmétique vrai non démontrable dans T ; codage des démonstrations.
  • Polycopié, pages 1 à 74.
  • Énoncé du partiel 2020.
  • feuille d'exercice 5 (hiérarchie arithmétique).
  • TD calculabilité et incomplétude (correction d'exercices de la feuille 3 et début de la feuille 4.
• Semaine 7 (26/10/2021) :
  • Mardi : complexité (à partir du 26/10, le cours du mardi est un cours de complexité).
  • Une théorie effectivement axiomatisable et complète est décidable ; l'ensemble des énoncés Π₁ vrais n'est pas semi-décidable ; premier théorème d'incomplétude de Gödel sous la forme : si une théorie T est effectivement axiomatisable et vérifie que tous les énoncés Π₁ démontrables sont vrais, alors il existe un énoncé Π₁ vrai non démontrable dans T.
  • Une théorie T est dite Σ-complète quand toutes les formules arithmétiques Σ₀ vraies sont démontrables dans T ; dans une théorie Σ-complète toutes les formules vraies Σ sont démontrables ; premier théorème d'incomplétude de Gödel sous la forme : si une théorie T est effectivement axiomatisable, Σ-complète et cohérente, alors il existe un énoncé Π₁ vrai non démontrable dans T.
  • Système d'axiomes de Robinson R^- (axiomatisation des formules Σ₀ vraies dans N); une théorie a pour conséquence R^- si et seulement si elle démontre toutes les formules arithmétiques Σ vraies, c'est-à-dire si et seulement si elle est Σ-complète.
  • Polycopié, pages 1 à 80.
• Semaine 8 ( 2/11/2021) :
  • Mardi : complexité
  • Jeudi 4/11 : TD complexité.
  • Système d'axiomes R (on ajoute à R^- le schéma d'axiomes qui exprime que tout élément standard est inférieur à tout élément non standard) ; arithmétique finiment axiomatisable Q de Robinson ; l'arithmétique de Robinson Q, et a fortiori l'arithmétique de Peano PA, ont pour conséquence R, en particulier elles sont Σ-complètes, c'est-à-dire que toutes les formules Σ vraies dans N sont démontrables dans Q (ainsi que PA).
  • Théorie Σ-cohérente (théories ne démontrant que des formules Σ₁ vraies dans N) ; existence de théories non Σ-cohérentes ; avatar du premier théorème d'incomplétude de Gödel : Si T est une théorie effectivement axiomatisable Σ-complète et Σ-cohérente, alors il existe un énoncé Π₁ non démontrable dans T et dont la négation n'est pas non plus démontrable dans T.
  • Ensembles faiblement/fortement représentables ; les ensembles semi-décidables sont faiblement représentables dans une théorie effectivement axiomatisable Σ-complète et Σ-cohérente ; théorème de Church indécidabilité de la théorie) sous hypothèse de Σ-cohérence ; les ensembles décidables sont fortement représentables dans une théorie effectivement axiomatisable Σ-complète et cohérente (astuce de Rosser), énoncé seulement.
  • Polycopié, pages 1 à 85.
• Semaine 9 (9/11/2021) :
  • Mardi : complexité
  • Jeudi : férié (11 novembre)
• Semaine 10 (16/11/2021) :
  • Mardi : complexité
  • TD calculabilité et incomplétude de 10h30 à 12h30; cours de 13h45 à 15h45 comme d'habitude.
  • Jeudi 18/11/2021 16h15-18h15, partiel Calculabilité et complexité, salle 247E, Halle à la Farine,programe du partiel : calculabilité, hiérarchie arithmétique (jusquà ~ p. 66 du polycopié).
  • Théorème d'indécidabilité de Church, et d'incomplétude de Gödel-Rosser : une théorie arithmétique cohérente qui étend R est indécidable, et donc, si de plus elle est effectivement axiomatisable, elle est incomplète.
  • Représentation des fonctions calculables
  • Un théorème de point fixe pour les formules ; formalisation de la preuve du premier théorème d'incomplétude, second théorème d'incomplétude ; conditions de démontrabilité de Bernays.
  • Polycopié, pages 1 à 89.
  • feuille d'exercice 6 (théorème de Gödel).
• Semaine 11 (23/11/2021) :
  • Mardi : complexité
  • Second théorème d'incomplétude : précisions ; équivalence démontrable entre la formule G du 1er théorème d'incomplétude pour la théorie T et la cohérence de T ; théorème de Löb.
  • Indécidabilité : Q est finiment axiomatisable et essentiellement indécidable(toutes ses extensions cohérentes sont indécidables) ; N muni des opérations usuelles est fortement indécidable, c'est-à-dire que toutes les théories ayant N pour modèle sont indécidables.
  • Polycopié, pages 1 à 93.
• Semaine 12 ( 30/11/2021) :
  • Mardi : complexité
  • Jeudi : TD 8h30-10h30 + cours de calculabilité et incomplétude 10h30-12h30, et 13h45-15h45.
  • Corrections des feuilles 5 et 6, corrigé de quelques exercices des feuilles 5 et 6.
  • Quelques résultats d'indécidabilité : l'arithmétique de Robinson dans le langage (0,s,+) est essentiellement indécidable ; il existe une sous-théorie finiment axiomatisable de ZF sans l'axiome de l'infini (ni l'xiome du choix, ni l'axiome de fondation) qui est essentiellement indécidable ; le calcul des prédicats égalitaire dans un langage avec au moins un symbole de prédicat binaire est indécidable.
  • Polycopié.
• Semaine 13 ( 7/12/2021) : rattrapages des cours du 14/09 et du 11/11
  • Mardi : TD complexité (1020)
  • Jeudi : cours calculabilité et incomplétude (2013) horaire habituel (13h45-15h45).
  • Correction du partiel (partie calculabilité).
• Semaine 14 ( 14/12/2021) :
  • examen de 14h à 17h - salle 1009, bâtiment Sophie Germain.
• Seconde session lundi 20/06/2022 :
  • examen de 2nde session lundi 20/06/2022 de 14h à 17h - salle 2011, bâtiment Sophie Germain (les notes de cours ne seront pas autorisées pour la seconde session).

Bibliographie

• René Cori, Daniel Lascar, Logique mathématique : cours et exercices (tome 2, Masson, 1993)
• Raymond Smullyan, Les théorèmes d'incomplétude de Gödel (Masson, 2000), trad. de Gödel incompletness theorems, Oxford University Press 92.
• Craig Smorynski, Logical Number Theory I : an Introduction (Springer Verlag, 1991)
• P. Odifreddi, Classical recursion theory (North Holland, 1989)
• Jean-Louis Krivine, Théorie des ensembles, (Cassini 1998 et 2007) chap. 9 (preuve sémantique du second théorème d'incomplétude).
• Jean-Yves Girard, Proof Theory and Logial Complexity, Bibliopolis (1987), chap 1 (en particulier le second théorème d'incomplétude dans PRA).
• Craig Smorynski, Self-Reference and Modal Logic, Springer Verlag (1985), chap. 0 (second théorème d'incomplétude dans PRA).

En dehors des deux premières références, ces livres couvrent largement plus sur le sujet que ce qui est abordé en cours.

Master

• Site du M2

dernière modification : lundi 20 mars 2023 12:44:18 CET