HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
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 Connect in order to contact the contributor
Submitted on : Thursday, October 19, 2006 - 9:10:31 AM
Last modification on : Friday, May 13, 2022 - 10:18:05 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