Continuous models of computation: from computability to complexity
- 11:00 2nd December 2015 ( week 8, Michaelmas Term 2015 )Room 441
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 my thesis, I 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.