Back to Search
Start Over
Elementarily computable functions over the real numbers and -sub-recursive functions
- Source :
-
Theoretical Computer Science . Dec2005, Vol. 348 Issue 2/3, p130-147. 18p. - Publication Year :
- 2005
-
Abstract
- 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. [Copyright &y& Elsevier]
Details
- Language :
- English
- ISSN :
- 03043975
- Volume :
- 348
- Issue :
- 2/3
- Database :
- Academic Search Index
- Journal :
- Theoretical Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 19044385
- Full Text :
- https://doi.org/10.1016/j.tcs.2005.09.010