Skip to Main content Skip to Navigation
Theses

Continuous models of computation: from computability to complexity

Résumé : 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. Cette 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.
Complete list of metadatas

Cited literature [121 references]  Display  Hide  Download

https://pastel.archives-ouvertes.fr/tel-01223284
Contributor : Amaury Pouly <>
Submitted on : Friday, May 27, 2016 - 7:04:22 PM
Last modification on : Monday, April 29, 2019 - 2:52:06 PM
Document(s) archivé(s) le : Sunday, August 28, 2016 - 11:15:18 AM

Identifiers

  • HAL Id : tel-01223284, version 2

Citation

Amaury Pouly. Continuous models of computation: from computability to complexity. Computational Complexity [cs.CC]. Ecole Doctorale Polytechnique; Universidad do Algarve, 2015. English. ⟨tel-01223284v2⟩

Share

Metrics

Record views

902

Files downloads

924