Intervenants : Laurent Bienvenu, Alexander Shen
En cette année 2012, qui célèbre les 100 ans après la naissance d’Alan Turing, nous présenterons les bases de la théorie qu’il a contribué à fonder, celle de la calculabilité. Nous rappellerons les concepts de base (machines de Turing, fonctions calculables) pour arriver rapidement à présenter quelques résultats et techniques fondamentaux de la calculabilité.
Le programme (prévisionnel) du cours est le suivant.
- Rappels de concepts de base
- Machines de Turing
- Ensembles et fonctions calculables, ensembles récursivement énumérables
- Indécidabilité
- Problème de l’arrêt. Indécidabilité, et many-one complétude
- Autres exemples de problèmes indécidables équivalents à l’arrêt:
équations diophantiennes, problème du mot dans les semi-groupes,
logique du premier ordre, etc.
- Oracles et réductions
- Machines de Turing à oracle
- Réduction Turing, degrés de Turing
- Hiérarchie arithmétique
- Le jump comme opérateur sur les degrés.
- Lemme de Schoenfield
- La hiérarchie arithmétique et ses liens avec l’opérateur de jump
- Complétude des ensembles \Sigma^0_n et \Pi^0_n, exemples de problèmes complets
- Résultats avancés sur les degrés
- Existence de degrés non comparables (2 preuves: par diagonalisation et probabiliste par le théorème de Sacks)
- Existence de deux degrés r.e. par la méthode de priorité de Friedberg-Muchnik
- Existence d’un degré de Turing minimal
- (Plus si le temps le permet: degrés « low », « high » et leur existence)
- Calculabilité sur les réels
- Définition des fonctions calculables sur les réels et leurs propriétés élémentaires
- Analyse calculable: théorèmes effectifs et non-effectifs
Les exposés seront donnés en anglais.
Dates : 16 au 20/01/2011
Planning:
– Lundi: 10h30-12h cours/TD; 14h-16h30 cours/TD
– Mardi: 10h-12h cours ; 14h-15h30 cours; 16h-17h30 TD
– Mercredi: 10h-12h cours ; 14h-15h30 cours; 16h-17h30 TD
– Jeudi: 10h-12h cours ; 14h-15h30 cours; 16h-17h30 TD
– Vendredi: 10h-12h cours ; 14h-15h30 cours; 16h-17h30 TD
Examen vendredi jusqu’à 18h3o (à confirmer)
Correspondante locale : Natacha Portier