Titre : Computing with analog models: On the complexity of solving differential equations
Exposant : Amaury Pouly
We will provide some results on the complexity of solving numerically
differential equations motivated by analog models of computation.
Classical models of computation, like Turing Machines, are typical discrete system:
they have discrete time and space. They also satisfy the so-called Church Thesis
which more or less guaranty that these models are all equivalent.
One can even extend this thesis to complexity classes in most cases.
On the contrary, analog models of computations are much less understood.
A typical example is the General Purpose Analog Computer (GPAC)
introduced by Claude Shanon in 1941. This model, equivalent to computing with
some differential equations, features both continuous time and space.
It is known that this model of computation is not more powerful than
a Turing machine when it comes to computability, and conversely,
any Turing Machine can be simulated with a GPAC. However,
the situation is less clear when one try to extend the comparison to complexity.