Thématiques de Recherche

Le groupe de travail Calculabilités fait partie du GDR Informatique Mathématique.

Les thèmes principaux de notre groupe de travail sont les suivants :

1. Calculabilité classique

• Réductions,
• Degrés,
• Hiérarchies,
• Méthodes de priorité.

2. Autres modèles de calcul

• Modèles géométriques : pavages, machines à signaux.
• Modèles algébriques : Abstract State Machines.
• Modèles dynamiques et distribués : automates cellulaires, protocoles de population, tas de sable.
• Calcul à temps continu,
• Calcul à temps ordinal.
• Calcul sur les structures infinies : réels, ordres.

3. Applications et interactions de la calculabilité

• Apport d’un cadre théorique formel à différents domaines :
  • Cryptologie
  • Sécurité
  • Résistance aux erreurs et aux pannes
  • Virologie
  • Théorie de l’information et de l’aléatoire (complexité de Kolmogorov)

4. Interactions avec d’autres domaines

• Complexité algorithmique
• Théorie des modèles
• Mathématiques à rebours
• Théorie des ensembles : modèles intérieurs, forcing, théorie descriptive, détermination