Calculabilité

Degrés Turing, théorie algorithmique de l'aléatoire, mathématiques à rebours, hypercalculabilité

Ce livre est en rupture d'impression, mais une version PDF est disponible en téléchargement gratuit ici. Une version anglaise étendue du livre est en cours de parution à Perspectives in Logic.

Table des matières

  1. Préambule
  2. Remerciements
  3. Introduction
  4. Infinis de Cantor

Calculabilité classique

  1. Fondements de la calculabilité
  2. Degrés Turing
  3. Hiérarchie arithmétique
  4. La thèse de Church-Turing
  5. Immunité et croissance de fonction
  6. Classes Π0 1 et degrés PA
  7. Interlude formel
  8. Forcing de Cohen
  9. Forcing effectif
  10. La quête de degrés naturels
  11. Méthode de priorité et degrés c. e.
  12. Structure des degrés Turing

Aléatoire algorithmique

  1. Introduction
  2. Complexité de Kolmogorov et nombres aléatoires
  3. Boréliens, mesure et calculabilité
  4. Aléatoire au sens de Martin-Löf
  5. Autres notions d’aléatoire
  6. Les K-triviaux

Mathématiques à rebours

  1. Introduction
  2. Arithmétique du second ordre
  3. Induction et conservation
  4. Réductions calculatoires
  5. Théorème de Ramsey

Hypercalculabilité

  1. Introduction
  2. Nombres transfinis
  3. Ensembles hyperarithmétiques
  4. Au delà des hyperarithmétiques
  5. Classes Σ1 1 et Π1 1
  6. Les systèmes ATR0 et Π1 1-CA0

Annexes

  1. Correction des exercices
  2. BibliographieNotations
  3. Index