Continuous models of computation: from computability to complexity
Amaury Pouly · HAL (Le Centre pour la Communication Scientifique Directe) · 2015
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 beimplemented in practice through the use of analog electronics ormechanical devices. It can be proved that the functions computed by a GPAC are preciselythe solutions of a special class of differential equations where the right-hand sideis 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 andthe GPAC have the same computational power. However, this result did not shed anylight 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 ofP and Computable Analysis.