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
2nd APPSEM II Workshop - APPSEM'2004, 2004, Tallinn, Estonia, 12 p, 2004
Liste complète des métadonnées

https://hal.inria.fr/inria-00099897
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 10:04:53
Dernière modification le : jeudi 11 janvier 2018 - 06:19:59

Identifiants

  • HAL Id : inria-00099897, version 1

Collections

Citation

Olivier Bournez, Emmanuel Hainry. An analog Characterization of Elementarily Computable Functions Over the Real Numbers. 2nd APPSEM II Workshop - APPSEM'2004, 2004, Tallinn, Estonia, 12 p, 2004. 〈inria-00099897〉

Partager

Métriques

Consultations de la notice

145