3539 articles – 5263 Notices  [english version]

inria-00099897, version 1

An analog Characterization of Elementarily Computable Functions Over the Real Numbers

Olivier Bournez () a, 1, Emmanuel Hainry () b, 1

2nd APPSEM II Workshop - APPSEM'2004 (2004) 12 p

  • a –  INRIA
  • b –  INPL
  • 1 :  PROTHEO (INRIA Lorraine - LORIA)

  • INRIA – CNRS : UMR7503 – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine (INPL) France

Références bibliographiques

  • Type de publication : Communications avec actes
  • Domaine : Informatique/Autre
  • Titre : An analog Characterization of Elementarily Computable Functions Over the Real Numbers
  • Résumé : 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.
  • Langue du document : Anglais
  • Date de publication : 2004
  • Audience : internationale
  • Titre conférence : 2nd APPSEM II Workshop - APPSEM'2004
  • Ville : Tallinn, Estonia
  • Date conférence : 2004
  • Editeur commercial : none
  • Pagination : 12 p
  • Mots-clés : analog models – complexity – computability || modèles analogiques – complexité – calculabilité
  • Commentaire : Colloque avec actes et comité de lecture. internationale.
  • Référence interne : A04-R-289 || bournez04b
 
  • inria-00099897, version 1
  • http://hal.inria.fr/inria-00099897
  • oai:hal.inria.fr:inria-00099897
  • Contributeur : Publications Loria <>
  • Soumis le : Mardi 26 Septembre 2006, 10:04:53
  • Dernière modification le : Jeudi 28 Septembre 2006, 15:22:46