Continuous models of computation: from computability to complexity

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.
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
Long-term archiving on : 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

739

Files downloads

666