Skip to Main content Skip to Navigation
Conference papers

Computability, Complexity and Programming with Ordinary Differential Equations

Abstract : Ordinary Differential Equations (ODEs) appear to be a universally adopted and very natural way for expressing properties for continuous time dynamical systems. They are intensively used, in particular in applied sciences. There exists an abundant literature about the hardness of solving ODEs with numerical methods. We adopt a dual view: we consider ODEs as a way to program or to describe our mathematical/computer science world. We survey several results considering ODEs under this computational perspective, with a computability and complexity theory point of view. In particular, we provide various reasons why polynomial ODEs should be considered as the continuous time analog of Turing machines for continuous-time computations, or should be used as a way to talk about mathematical logic. This has already applications in various fields: determining whether analog models of computation can compute faster than classical digital models of computation; solving complexity issues for computations with biochemical reactions in bioinformatics; machine independent characterizations of various computability and complexity classes such as PTIME or NPTIME, or proof of the existence of a universal polynomial ordinary differential equation whose solutions can approximate any continuous function if provided with a suitable well-chosen initial condition.
Document type :
Conference papers
Complete list of metadata
Contributor : Olivier Bournez Connect in order to contact the contributor
Submitted on : Friday, May 13, 2022 - 10:29:06 PM
Last modification on : Tuesday, May 31, 2022 - 3:38:58 AM


Publisher files allowed on an open archive




Olivier Bournez. Computability, Complexity and Programming with Ordinary Differential Equations. 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020), 2020, Montpellier, France. ⟨10.4230/LIPIcs.STACS.2020.3⟩. ⟨hal-03668004⟩



Record views


Files downloads