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.

  1. Rappels de concepts de base
    • Machines de Turing
    • Ensembles et fonctions calculables, ensembles récursivement énumérables
  2. 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.
  3. Oracles et réductions
    • Machines de Turing à oracle
    • Réduction Turing, degrés de Turing
  4. 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
  5. 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)
  6. 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