Elementarily Computable Functions Over the Real Numbers and $\mathbb{R}$-Sub-Recursive Functions

Olivier Bournez 1 Emmanuel Hainry 1
1 PROTHEO - Constraints, automatic deduction and software properties proofs
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : We present an analog and machine-independent algebraic characterization of elementarily computable functions over the real numbers in the sense of recursive analysis: we prove that they correspond to the smallest class of functions that contains some basic functions, and closed by composition, linear integration, and a simple limit schema. We generalize this result to all higher levels of the Grzegorczyk Hierarchy. This paper improves several previous partial characterizations and has a dual interest: - Concerning recursive analysis, our results provide %fully machine-in­de­pen­dent characterizations of natural classes of computable functions over the real numbers, allowing to define these classes without usual considerations on higher-order (type $2$) Turing machines. - Concerning analog models, our results provide a characterization of the power of a natural class of analog models over the real numbers and provide new insights for understanding the relations between several analog computational models.
Type de document :
[Intern report] A04-R-301 || bournez04f, 2004, 22 p
Liste complète des métadonnées

Contributeur : Publications Loria <>
Soumis le : jeudi 19 octobre 2006 - 09:10:31
Dernière modification le : vendredi 9 février 2018 - 10:48:04
Document(s) archivé(s) le : vendredi 25 novembre 2016 - 12:28:13


  • HAL Id : inria-00107812, version 1



Olivier Bournez, Emmanuel Hainry. Elementarily Computable Functions Over the Real Numbers and $\mathbb{R}$-Sub-Recursive Functions. [Intern report] A04-R-301 || bournez04f, 2004, 22 p. 〈inria-00107812〉



Consultations de la notice


Téléchargements de fichiers