Skip to Main content Skip to Navigation

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.
Document type :
Complete list of metadata
Contributor : Publications Loria <>
Submitted on : Thursday, October 19, 2006 - 9:10:31 AM
Last modification on : Friday, February 26, 2021 - 3:28:06 PM
Long-term archiving on: : Friday, November 25, 2016 - 12:28:13 PM


  • 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⟩



Record views


Files downloads