### 17 juin 2019

**Amaury Pouly**(IRIF - CNRS)

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 talk, I will present results from my thesis that 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.

I will present some recent work on the universality of polynomial

differential equations. We show that when we impose no restrictions at

all on the system, it is possible to build a fixed equation that

is universal in the sense it can approximate arbitrarily well any

continuous curve over R, simply by changing the initial condition of

the system.

If time allows, I will also mention some recent application of this

work to show that chemical reaction networks are strongly Turing

complete with the differential semantics.