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

Elementarily Computable Functions Over the Real Numbers and $mathbb{R}$-Sub-Recursive Functions - Download this document for free, or read online. Document in PDF available to download.

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.

Mots-clés : modèles analogiques computability analog models calculabilité

Author: Olivier Bournez - Emmanuel Hainry -

Source: https://hal.archives-ouvertes.fr/


Related documents