Amaury Pouly (Oxford, UK)

En 1941, Claude Shannon définit le General Purpose Analog Computer (GPAC), un modèle de calcul analogique à temps continu. Le GPAC est un modèle réaliste car il peut être construit mécaniquement ou bien à l’aide circuit électroniques. Il s’avère que les fonctions calculables par ce modèle sont exactement les solutions d’une certaine classe d’équations différentielles à second membre polynomial. Bien que les ordinateurs digitaux aient remplacé les ordinateurs analogiques, la question de savoir si ces modèles sont comparables reste en suspens.

Il y a quelques années, cette thématique est réapparue à l’occasion d’une preuvre montrant que le GPAC et les machines de Turing ont la même puissance de calcul. Toutefois ce résultat ne nous aide guère à comprendre la relation entre ces deux modèles au niveau de la complexité des calculs. En d’autres termes, les ordinateurs analogiques ne calculent pas plus de fonctions que les ordinateurs classiques, mais il se pourrait qu’ils les calculent plus vite. Cette problématique est intrinsèquement reliée à celle, fondamentale, de la définition même de la complexité d’un système à temps et espace continu. En effet, ces systèmes exhibent le paradoxe troublant de Zenon, c’est à dire celui de la contraction de l’espace et du temps.

Ma thèse apporte des réponses fondamentales à ces questions. Nous montrons que la complexité d’un calcul par le GPAC peut être mesurée par la longueur de la courbe ainsi définie. Nous montrons ensuite que le GPAC et les machines de Turing ont la même puissance de calcul au niveau de la complexité. Enfin nous donnons une caractérisation purement analogique, et indépendante de toute notion de machine, de la classe P ainsi que de l’analyse récursive.