An Analog Characterization of Elementarily Computable Functions over the Real Numbers
Identifieur interne : 006F47 ( Main/Merge ); précédent : 006F46; suivant : 006F48An Analog Characterization of Elementarily Computable Functions over the Real Numbers
Auteurs : Olivier Bournez [France] ; Emmanuel Hainry [France]Source :
- Lecture Notes in Computer Science [ 0302-9743 ]
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. 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.
Url:
DOI: 10.1007/978-3-540-27836-8_25
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 000772
- to stream Istex, to step Curation: 000767
- to stream Istex, to step Checkpoint: 001852
Links to Exploration step
ISTEX:224F4E3791E016329022A49FCE5042BCD856A549Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">An Analog Characterization of Elementarily Computable Functions over the Real Numbers</title><author><name sortKey="Bournez, Olivier" sort="Bournez, Olivier" uniqKey="Bournez O" first="Olivier" last="Bournez">Olivier Bournez</name></author><author><name sortKey="Hainry, Emmanuel" sort="Hainry, Emmanuel" uniqKey="Hainry E" first="Emmanuel" last="Hainry">Emmanuel Hainry</name></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:224F4E3791E016329022A49FCE5042BCD856A549</idno><date when="2004" year="2004">2004</date><idno type="doi">10.1007/978-3-540-27836-8_25</idno><idno type="url">https://api.istex.fr/ark:/67375/HCB-F9JV6XHD-P/fulltext.pdf</idno><idno type="wicri:Area/Istex/Corpus">000772</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">000772</idno><idno type="wicri:Area/Istex/Curation">000767</idno><idno type="wicri:Area/Istex/Checkpoint">001852</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">001852</idno><idno type="wicri:doubleKey">0302-9743:2004:Bournez O:an:analog:characterization</idno><idno type="wicri:Area/Main/Merge">006F47</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">An Analog Characterization of Elementarily Computable Functions over the Real Numbers</title><author><name sortKey="Bournez, Olivier" sort="Bournez, Olivier" uniqKey="Bournez O" first="Olivier" last="Bournez">Olivier Bournez</name><affiliation wicri:level="3"><country xml:lang="fr">France</country><wicri:regionArea>LORIA/INRIA, 615 Rue du Jardin Botanique, BP101, 54602, Villers lès Nancy</wicri:regionArea><placeName><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region><settlement type="city">Villers lès Nancy</settlement></placeName></affiliation><affiliation wicri:level="1"><country wicri:rule="url">France</country></affiliation></author><author><name sortKey="Hainry, Emmanuel" sort="Hainry, Emmanuel" uniqKey="Hainry E" first="Emmanuel" last="Hainry">Emmanuel Hainry</name><affiliation wicri:level="3"><country xml:lang="fr">France</country><wicri:regionArea>LORIA/INRIA, 615 Rue du Jardin Botanique, BP101, 54602, Villers lès Nancy</wicri:regionArea><placeName><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region><settlement type="city">Villers lès Nancy</settlement></placeName></affiliation><affiliation wicri:level="1"><country wicri:rule="url">France</country></affiliation></author></analytic><monogr></monogr><series><title level="s" type="main" xml:lang="en">Lecture Notes in Computer Science</title><idno type="ISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="ISSN">0302-9743</idno></series></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0302-9743</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">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. 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.</div></front></TEI></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Merge
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 006F47 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Merge/biblio.hfd -nk 006F47 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Main
|étape= Merge
|type= RBID
|clé= ISTEX:224F4E3791E016329022A49FCE5042BCD856A549
|texte= An Analog Characterization of Elementarily Computable Functions over the Real Numbers
}}
| This area was generated with Dilib version V0.6.33. |  |