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 :
- Calculabilité classique : réductions, degrés, hiérarchies, méthodes de priorité.
- Autres modèles de calculs : 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).
- 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).
- 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), théorie des domaines.