On december 7th 2006, I defended my PhD thesis entitled

Modèles de calcul sur les réels, résultats de comparaison

in front of the following jury:

• 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)

Abstract

Computation on the real numbers can be modelised in several different ways. There indeed exist a lot of different computation models on the reals. However, there are few results for comparing those models, and most of these results are incomparability results. The case of computation over the reals hence is quite different from the classical case where Church thesis claims that all reasonable models compute exactly the same functions.

We show that recursively computable functions (in the sense of computable analysis) can be shown equivalent to some adequately defined class of R-recursive functions, and also to GPAC-computable functions.

More than an analog characterization of recursively enumerable functions, we show that the limit operator we defined can be used to provide an analog characterization of elementarily computable functions and functions from Grzegorczyk’s hierarchy.

Those results can be seen as a first step toward a unification of computable functions over the reals.

Download

The manuscript can be downloaded in french.

Award

This thesis was awarded the “Prix de thèse de l’INPL” 2007.