January 30, 2012
Antoine Taveneaux (LIAFA)Dans de nombreux théorèmes mathématiques, le quantificateur existentiel n’est pas “effectif”, dans le sens où l’objet dont on prouve l’existence n’est pas calculable.
La théorie de la calculabilité porte principalement sur la comparaison des ensembles d’entiers, du point de vue de leur calculabilité mutuelle. Nous verrons que l’on peut aussi comparer l’effectivité des théorèmes, et faire en quelque sorte de la “calculabilité sur les théorèmes”. Cette exposé sera une introduction informelle qui s’adresse donc à un public assez large et ne suppose presque aucun prérequis en théorie de la calculabilité.