Computational bounds on polynomial differential equations - Graça, Daniel (2012)
In this paper we study from a computational perspective some prop-erties of the solutions of polynomial ordinary di erential equations. We consider elementary (in the sense of Analysis) discrete-time dynam-ical systems satisfying certain criteria of robustness. We show that those systems can be simulated with elementary and robust continuous-time dynamical systems which can be expanded into fully polynomial ordinary diferential equations with coe cients in Q[ ]. This sets a computational lower bound on polynomial ODEs since the former class is large enough to include the dynamics of arbitrary Turing machines. We also apply the previous methods to show that the problem of de-termining whether the maximal interval of defnition of an initial-value problem defned with polynomial ODEs is bounded or not is in general undecidable, even if the parameters of the system are computable and comparable and if the degree of the corresponding polynomial is at most 56. Combined with earlier results on the computability of solutions of poly-nomial ODEs, one can conclude that there is from a computational point of view a close connection between these systems and Turing machines.