Document Actions

Gilles Dowek (seminar)

Gilles Dowek (LIX) gives a seminar talk on vector spaces and computability

Mercredi 17 février, 11h, batiment I
Centre de Recherche Commun INRIA - Microsoft Research

Espaces vectoriels et calculabilité
Gilles Dowek
Ecole polytechnique

Espaces vectoriels et calculabilité

Cet exposé sera consacré à deux résultats (l'un et l'autre communs avec Pablo Arrighi) qui mettent en lien les notions d'espace vectoriel et d'algorithme. Le premier montre que les axiomes des espaces vectoriels peuvent être orientés et complétés pour former un algorithme de réduction d'une expression vectorielle en une combinaison linéaire des variables, algorithme qui est à la base de la sémantique opérationnelle du langage quantique Lineal. Le second, qui est plus récent, montre que la notion de calculabilité d'une fonction d'un espace vectoriel dans un autre est indépendante du choix d'une numérotation des vecteurs, pour les espaces vectoriels de "dimension tensorielle" finie même s'ils sont de "dimension vectorielle" infinie. Ce résultat permet de définir une notion de complétude pour un langage quantique et un équivalent de la thèse de Church pour le calcul quantique.

Personal tools