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.
Type de document :
Thèse
Computational Complexity [cs.CC]. Ecole Doctorale Polytechnique; Universidad do Algarve, 2015. English
Liste complète des métadonnées

Littérature citée [121 références]  Voir  Masquer  Télécharger

https://pastel.archives-ouvertes.fr/tel-01223284
Contributeur : Amaury Pouly <>
Soumis le : vendredi 27 mai 2016 - 19:04:22
Dernière modification le : jeudi 10 mai 2018 - 02:06:51
Document(s) archivé(s) le : dimanche 28 août 2016 - 11:15:18

Fichier

Identifiants

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

Partager

Métriques

Consultations de la notice

659

Téléchargements de fichiers

548