J’ai soutenu le 7 décembre 2006 ma thèse intitulée
Modèles de calcul sur les réels, résultats de comparaison
devant le jury composé de
- Vincent Blondel (président du jury)
- Serge Grigorieff (rapporteur)
- Giuseppe Longo (rapporteur)
- Olivier Bournez (co-encadrant)
- José Félix Costa (examinateur)
- Jean-Paul Haton (examinateur)
- Jean-Yves Marion (directeur de thèse)
Résumé
Il existe de nombreux modèles de calcul sur les réels. Ces différents modèles calculent diverses fonctions, certains sont plus puissants que d’autres, certains sont deux à deux incomparables. Le calcul sur les réels est donc de ce point de vue bien différent du calcul sur les entiers qui est unifié par la thèse de Church-Turing qui affirme que tous les modèles raisonnables calculent les mêmes fonctions.
Les résultats de cette thèse sont de deux sortes. Premièrement, nous montrons des équivalences entre les fonctions récursivement calculables et une certaine classe de fonctions R-récursives et entre les fonctions GPAC-calculables et les fonctions récursivement calculables. Ces deux résultats ne sont cependant valables que si les fonctions présentent quelques caractéristiques : elles doivent être définies sur un compact et dans le premier cas être de classe C2. Deuxièmement, nous montrons également une hiérarchie de classes de fonctions R-récursives qui caractérisent les fonctions élémentairement calculables, les fonctions En-calculables pour n≥3 (où les En sont les fonctions de la hiérarchie de Grzegorczyk), et des fonctions récursivement calculables. Ce résultat utilise un opérateur de limite dont nous avons prouvé la généralité en montrant qu’il transfère une inclusion sur la partie discrète des fonctions en une inclusion sur les fonctions sur les réels elles-mêmes.
Ces résultats constituent donc une avancée vers une éventuelle unification des modèles de calcul sur les réels.
Téléchargement
La version définitive du manuscrit est disponible.
Récompense
J’ai obtenu pour ce travail le “prix de thèse de l’INPL 2007”.