Continuous models of computation: from computability to complexity
Modèles de calculs à temps continu: de la calculabilité à la complexité
Résumé
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.
Loading...