An analog Characterization of Elementarily Computable Functions Over the Real Numbers

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 characterizations 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. 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.
Type de document :
Communication dans un congrès
Diaz, Josep and Karhumäki, Juhani and Lepisto, Arto and Sannella, Donald Theodore. 31st International Colloqiuim on Automata, Languages and Programming - ICALP'2004, 2004, Turku, Finland, Springer, 3142, pp.269-280, 2004, Lecture Notes in Computer Science
Liste complète des métadonnées

https://hal.inria.fr/inria-00100054
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 10:13:44
Dernière modification le : vendredi 9 février 2018 - 10:48:04

Identifiants

  • HAL Id : inria-00100054, version 1

Collections

Citation

Olivier Bournez, Emmanuel Hainry. An analog Characterization of Elementarily Computable Functions Over the Real Numbers. Diaz, Josep and Karhumäki, Juhani and Lepisto, Arto and Sannella, Donald Theodore. 31st International Colloqiuim on Automata, Languages and Programming - ICALP'2004, 2004, Turku, Finland, Springer, 3142, pp.269-280, 2004, Lecture Notes in Computer Science. 〈inria-00100054〉

Partager

Métriques

Consultations de la notice

171