Polynomial differential equations compute all real computable functions on computable compact intervals

Olivier Bournez 1 Manuel L. Campagnolo Daniel S. Graça Emmanuel Hainry 1
1 CARTE - Theoretical adverse computations, and safety
Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
Abstract : In the last decade, there have been several attempts to understand the relations between the many models of analog computation. Unfortunately, most models are not equivalent. Euler's Gamma function, which is computable according to computable analysis, but that cannot be generated by Shannon's General Purpose Analog Computer (GPAC), has often been used to argue that the GPAC is less powerful than digital computation. However, when computability with GPACs is not restricted to real-time generation of functions, it has been shown recently that Gamma becomes computable by a GPAC. Here we extend this result by showing that, in an appropriate framework, the GPAC and computable analysis are actually equivalent from the computability point of view, at least in compact intervals. Since GPACs are equivalent to systems of polynomial differential equations then we show that all real computable functions over compact intervals can be defined by such models.
Type de document :
Article dans une revue
Journal of Complexity, Elsevier, 2007, 23 (3), pp.317-335. 〈10.1016/j.jco.2006.12.005〉
Liste complète des métadonnées

https://hal.inria.fr/inria-00102947
Contributeur : Olivier Bournez <>
Soumis le : lundi 2 octobre 2006 - 22:38:33
Dernière modification le : mardi 18 décembre 2018 - 16:48:02

Lien texte intégral

Identifiants

Collections

Citation

Olivier Bournez, Manuel L. Campagnolo, Daniel S. Graça, Emmanuel Hainry. Polynomial differential equations compute all real computable functions on computable compact intervals. Journal of Complexity, Elsevier, 2007, 23 (3), pp.317-335. 〈10.1016/j.jco.2006.12.005〉. 〈inria-00102947v1〉

Partager

Métriques

Consultations de la notice

203