Laboratoire d'informatique de l'École polytechnique

Sémin'Ouvert : «Continuous Time Models of Computation» par Olivier Bournez

Speaker: Olivier Bournez
Location: Amphithéâtre Sophie Germain
Date: Thu, 22 Sep 2016, 14:30-15:30

Le Sémin'Ouvert est une série de séminaires internes au LIX destiné à favoriser les échanges scientifiques entre les équipes du laboratoire. Les présentations sont abordables et adaptées à un public varié. Les différentes équipes du LIX interviennent tout au long de l'année pour y présenter des résultats marquants, ou états de l'art sur des domaines qui leur sont propres.

Pour commencer cette série, nous aurons le plaisir d'écouter un exposé d'Olivier Bournez (équipe AlCo du LIX), intitulé Continuous Time Models of Computation, qui se tiendra le jeudi 22 septembre 2016, à 14h30 dans l'amphithéâtre Sophie Germain du bâtiment Turing.

Résumé:

Modern models of computation (for example Turing machines) are digital. But analog machines and models also exist. In particular, first models of computation were analog. We will describe some old and recent models and we will present results about how these models can be compared to digital modern ones. In particular, we will show that polynomial ordinary differential equations have very nice and unexpected properties. In particular, P (polynomial time) corresponds unexpectedly to solutions of polynomial lengths of polynomial ordinary differential equations, and hence can be defined without any reference to any notion of a machine.