Skip to Main content Skip to Navigation
Journal articles

Elementarily Computable Functions Over the Real Numbers and 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 machine-independent 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.
Document type :
Journal articles
Complete list of metadatas
Contributor : Olivier Bournez <>
Submitted on : Wednesday, October 26, 2005 - 7:00:55 PM
Last modification on : Thursday, March 5, 2020 - 11:02:16 AM


  • HAL Id : inria-00000518, version 1



Olivier Bournez, Emmanuel Hainry. Elementarily Computable Functions Over the Real Numbers and R-Sub-Recursive Functions. Theoretical Computer Science, Elsevier, 2005, 348 (2-3), pp.130--147. ⟨inria-00000518⟩



Record views