Continuous models of computation: from computability to complexity - Archive ouverte HAL Access content directly
Theses Year : 2015

Continuous models of computation: from computability to complexity

Modèles de calculs à temps continu: de la calculabilité à la complexité

(1)
1

Abstract

In 1941, Claude Shannon introduced a continuous-time analog model of computation, namely the General Purpose Analog Computer (GPAC). The GPAC is a physically feasible model in the sense that it can be implemented in practice through the use of analog electronics or mechanical devices. It can be proved that the functions computed by a GPAC are precisely the solutions of a special class of differential equations where the right-hand side is a polynomial. Analog computers have since been replaced by digital counterpart. Nevertheless, one can wonder how the GPAC could be compared to Turing machines. A few years ago, it was shown that Turing-based paradigms and the GPAC have the same computational power. However, this result did not shed any light on what happens at a computational complexity level. In other words, analog computers do not make a difference about what can be computed; but maybe they could compute faster than a digital computer. A fundamental difficulty of continuous-time model is to define a proper notion of complexity. Indeed, a troubling problem is that many models exhibit the so-called Zeno's phenomenon, also known as space-time contraction. In this thesis, we give several fundamental contributions to these questions. We show that the GPAC has the same computational power as the Turing machine, at the complexity level. We also provide as a side effect a purely analog, machine-independent characterization of P and Computable Analysis.
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.
Fichier principal
Vignette du fichier
thesis.pdf (1.97 Mo) Télécharger le fichier
Loading...

Dates and versions

tel-01223284 , version 1 (02-11-2015)
tel-01223284 , version 2 (27-05-2016)

Identifiers

  • HAL Id : tel-01223284 , version 2

Cite

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

Share

Gmail Facebook Twitter LinkedIn More