Polynomial differential equations compute all real computable functions on computable compact intervals
Identifieur interne : 004A43 ( Main/Exploration ); précédent : 004A42; suivant : 004A44Polynomial differential equations compute all real computable functions on computable compact intervals
Auteurs : Olivier Bournez [France] ; Manuel L. Campagnolo [Portugal] ; Daniel S. Graça [Portugal] ; Emmanuel Hainry [France]Source :
- Journal of Complexity [ 0885-064X ] ; 2007.
English descriptors
- mix :
Abstract
In the last decade, the field of analog computation has experienced renewed interest. In particular, there have been several attempts to understand which relations exist between the many models of analog computation. Unfortunately, most models are not equivalent. It is known that Euler's Gamma function is computable according to computable analysis, while it cannot be generated by Shannon's General Purpose Analog Computer (GPAC). This example has often been used to argue that the GPAC is less powerful than digital computation. However, as we will demonstrate, when computability with GPACs is not restricted to real-time generation of functions, we obtain two equivalent models of analog computation. Using this approach, it has been shown recently that the Gamma function becomes computable by a GPAC \cite{Gra04}. Here we extend this result by showing that, in an appropriate framework, the GPAC and computable analysis are actually equivalent from the computability point of view, at least in compact intervals. Since GPACs are equivalent to systems of polynomial differential equations then we show that all real computable functions over compact intervals can be defined by such models.
Url:
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Hal, to step Corpus: 003C19
- to stream Hal, to step Curation: 003C19
- to stream Hal, to step Checkpoint: 003D03
- to stream Main, to step Merge: 005001
- to stream Hal, to step Corpus: 003C20
- to stream Hal, to step Curation: 003C20
- to stream Hal, to step Checkpoint: 003D02
- to stream Main, to step Merge: 004B80
- to stream Main, to step Curation: 004A43
Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Polynomial differential equations compute all real computable functions on computable compact intervals</title><author><name sortKey="Bournez, Olivier" sort="Bournez, Olivier" uniqKey="Bournez O" first="Olivier" last="Bournez">Olivier Bournez</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-2071" status="VALID"><orgName>Laboratoire d'informatique de l'École polytechnique [Palaiseau]</orgName><orgName type="acronym">LIX</orgName><desc><address><addrLine>Route de Saclay 91128 PALAISEAU CEDEX</addrLine><country key="FR"></country></address><ref type="url">http://www.lix.polytechnique.fr/</ref></desc><listRelation><relation active="#struct-300340" type="direct"></relation><relation name="UMR7161" active="#struct-441569" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-300340" type="direct"><org type="institution" xml:id="struct-300340" status="VALID"><orgName>Polytechnique - X</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle><tutelle name="UMR7161" active="#struct-441569" type="direct"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle></tutelles></hal:affiliation><country>France</country></affiliation></author><author><name sortKey="Campagnolo, Manuel L" sort="Campagnolo, Manuel L" uniqKey="Campagnolo M" first="Manuel L." last="Campagnolo">Manuel L. Campagnolo</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-46039" status="VALID"><orgName>Instituto Superior Técnico - Technical University of Lisbon</orgName><orgName type="acronym">IST</orgName><desc><address><addrLine>R. Alves Redol, n.9, 1000–129 Lisboa</addrLine><country key="PT"></country></address><ref type="url">http://www.ist.utl.pt/</ref></desc><listRelation><relation active="#struct-368878" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-368878" type="direct"><org type="institution" xml:id="struct-368878" status="INCOMING"><orgName>Technical University of Lisbon</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle></tutelles></hal:affiliation><country>Portugal</country></affiliation></author><author><name sortKey="Graca, Daniel S" sort="Graca, Daniel S" uniqKey="Graca D" first="Daniel S." last="Graça">Daniel S. Graça</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-46039" status="VALID"><orgName>Instituto Superior Técnico - Technical University of Lisbon</orgName><orgName type="acronym">IST</orgName><desc><address><addrLine>R. Alves Redol, n.9, 1000–129 Lisboa</addrLine><country key="PT"></country></address><ref type="url">http://www.ist.utl.pt/</ref></desc><listRelation><relation active="#struct-368878" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-368878" type="direct"><org type="institution" xml:id="struct-368878" status="INCOMING"><orgName>Technical University of Lisbon</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle></tutelles></hal:affiliation><country>Portugal</country></affiliation></author><author><name sortKey="Hainry, Emmanuel" sort="Hainry, Emmanuel" uniqKey="Hainry E" first="Emmanuel" last="Hainry">Emmanuel Hainry</name><affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-29797" status="VALID"><idno type="RNSR">200918992J</idno><orgName>Theoretical adverse computations, and safety</orgName><orgName type="acronym">CARTE</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.inria.fr/equipes/carte</ref></desc><listRelation><relation active="#struct-129671" type="direct"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-423084" type="direct"></relation><relation active="#struct-206040" type="indirect"></relation><relation active="#struct-413289" type="indirect"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation></listRelation><tutelles><tutelle active="#struct-129671" type="direct"><org type="laboratory" xml:id="struct-129671" status="VALID"><idno type="RNSR">198618246Y</idno><orgName>INRIA Nancy - Grand Est</orgName><desc><address><addrLine>615 rue du Jardin Botanique 54600 Villers-lès-Nancy</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/nancy</ref></desc><listRelation><relation active="#struct-300009" type="direct"></relation></listRelation></org></tutelle><tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName><orgName type="acronym">Inria</orgName><desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/en/</ref></desc></org></tutelle><tutelle active="#struct-423084" type="direct"><org type="department" xml:id="struct-423084" status="VALID"><orgName>Department of Formal Methods </orgName><orgName type="acronym">LORIA - FM</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.loria.fr/la-recherche-en/departements/formal-methods</ref></desc><listRelation><relation active="#struct-206040" type="direct"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-413289" type="indirect"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation></listRelation></org></tutelle><tutelle active="#struct-206040" type="indirect"><org type="laboratory" xml:id="struct-206040" status="VALID"><idno type="IdRef">067077927</idno><idno type="RNSR">198912571S</idno><idno type="IdUnivLorraine">[UL]RSI--</idno><orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName><orgName type="acronym">LORIA</orgName><date type="start">2012-01-01</date><desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.loria.fr</ref></desc><listRelation><relation active="#struct-300009" type="direct"></relation><relation active="#struct-413289" type="direct"></relation><relation name="UMR7503" active="#struct-441569" type="direct"></relation></listRelation></org></tutelle><tutelle active="#struct-413289" type="indirect"><org type="institution" xml:id="struct-413289" status="VALID"><idno type="IdRef">157040569</idno><idno type="IdUnivLorraine">[UL]100--</idno><orgName>Université de Lorraine</orgName><orgName type="acronym">UL</orgName><date type="start">2012-01-01</date><desc><address><addrLine>34 cours Léopold - CS 25233 - 54052 Nancy cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.univ-lorraine.fr/</ref></desc></org></tutelle><tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city">Nancy</settlement><settlement type="city">Metz</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Université de Lorraine</orgName></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">HAL</idno><idno type="RBID">Hal:hal-00760984</idno><idno type="halId">hal-00760984</idno><idno type="halUri">https://hal-polytechnique.archives-ouvertes.fr/hal-00760984</idno><idno type="url">https://hal-polytechnique.archives-ouvertes.fr/hal-00760984</idno><date when="2007">2007</date><idno type="wicri:Area/Hal/Corpus">003C19</idno><idno type="wicri:Area/Hal/Curation">003C19</idno><idno type="wicri:Area/Hal/Checkpoint">003D03</idno><idno type="wicri:explorRef" wicri:stream="Hal" wicri:step="Checkpoint">003D03</idno><idno type="wicri:doubleKey">0885-064X:2007:Bournez O:polynomial:differential:equations</idno><idno type="wicri:Area/Main/Merge">005001</idno><idno type="wicri:source">HAL</idno><idno type="RBID">Hal:inria-00102947</idno><idno type="url">https://hal.inria.fr/inria-00102947</idno><idno type="wicri:Area/Hal/Corpus">003C20</idno><idno type="wicri:Area/Hal/Curation">003C20</idno><idno type="wicri:Area/Hal/Checkpoint">003D02</idno><idno type="wicri:explorRef" wicri:stream="Hal" wicri:step="Checkpoint">003D02</idno><idno type="wicri:doubleKey">0885-064X:2007:Bournez O:polynomial:differential:equations</idno><idno type="wicri:Area/Main/Merge">004B80</idno><idno type="wicri:Area/Main/Curation">004A43</idno><idno type="wicri:Area/Main/Exploration">004A43</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en">Polynomial differential equations compute all real computable functions on computable compact intervals</title><author><name sortKey="Bournez, Olivier" sort="Bournez, Olivier" uniqKey="Bournez O" first="Olivier" last="Bournez">Olivier Bournez</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-2071" status="VALID"><orgName>Laboratoire d'informatique de l'École polytechnique [Palaiseau]</orgName><orgName type="acronym">LIX</orgName><desc><address><addrLine>Route de Saclay 91128 PALAISEAU CEDEX</addrLine><country key="FR"></country></address><ref type="url">http://www.lix.polytechnique.fr/</ref></desc><listRelation><relation active="#struct-300340" type="direct"></relation><relation name="UMR7161" active="#struct-441569" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-300340" type="direct"><org type="institution" xml:id="struct-300340" status="VALID"><orgName>Polytechnique - X</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle><tutelle name="UMR7161" active="#struct-441569" type="direct"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle></tutelles></hal:affiliation><country>France</country></affiliation></author><author><name sortKey="Campagnolo, Manuel L" sort="Campagnolo, Manuel L" uniqKey="Campagnolo M" first="Manuel L." last="Campagnolo">Manuel L. Campagnolo</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-46039" status="VALID"><orgName>Instituto Superior Técnico - Technical University of Lisbon</orgName><orgName type="acronym">IST</orgName><desc><address><addrLine>R. Alves Redol, n.9, 1000–129 Lisboa</addrLine><country key="PT"></country></address><ref type="url">http://www.ist.utl.pt/</ref></desc><listRelation><relation active="#struct-368878" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-368878" type="direct"><org type="institution" xml:id="struct-368878" status="INCOMING"><orgName>Technical University of Lisbon</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle></tutelles></hal:affiliation><country>Portugal</country></affiliation></author><author><name sortKey="Graca, Daniel S" sort="Graca, Daniel S" uniqKey="Graca D" first="Daniel S." last="Graça">Daniel S. Graça</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-46039" status="VALID"><orgName>Instituto Superior Técnico - Technical University of Lisbon</orgName><orgName type="acronym">IST</orgName><desc><address><addrLine>R. Alves Redol, n.9, 1000–129 Lisboa</addrLine><country key="PT"></country></address><ref type="url">http://www.ist.utl.pt/</ref></desc><listRelation><relation active="#struct-368878" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-368878" type="direct"><org type="institution" xml:id="struct-368878" status="INCOMING"><orgName>Technical University of Lisbon</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle></tutelles></hal:affiliation><country>Portugal</country></affiliation></author><author><name sortKey="Hainry, Emmanuel" sort="Hainry, Emmanuel" uniqKey="Hainry E" first="Emmanuel" last="Hainry">Emmanuel Hainry</name><affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-29797" status="VALID"><idno type="RNSR">200918992J</idno><orgName>Theoretical adverse computations, and safety</orgName><orgName type="acronym">CARTE</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.inria.fr/equipes/carte</ref></desc><listRelation><relation active="#struct-129671" type="direct"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-423084" type="direct"></relation><relation active="#struct-206040" type="indirect"></relation><relation active="#struct-413289" type="indirect"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation></listRelation><tutelles><tutelle active="#struct-129671" type="direct"><org type="laboratory" xml:id="struct-129671" status="VALID"><idno type="RNSR">198618246Y</idno><orgName>INRIA Nancy - Grand Est</orgName><desc><address><addrLine>615 rue du Jardin Botanique 54600 Villers-lès-Nancy</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/nancy</ref></desc><listRelation><relation active="#struct-300009" type="direct"></relation></listRelation></org></tutelle><tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName><orgName type="acronym">Inria</orgName><desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/en/</ref></desc></org></tutelle><tutelle active="#struct-423084" type="direct"><org type="department" xml:id="struct-423084" status="VALID"><orgName>Department of Formal Methods </orgName><orgName type="acronym">LORIA - FM</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.loria.fr/la-recherche-en/departements/formal-methods</ref></desc><listRelation><relation active="#struct-206040" type="direct"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-413289" type="indirect"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation></listRelation></org></tutelle><tutelle active="#struct-206040" type="indirect"><org type="laboratory" xml:id="struct-206040" status="VALID"><idno type="IdRef">067077927</idno><idno type="RNSR">198912571S</idno><idno type="IdUnivLorraine">[UL]RSI--</idno><orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName><orgName type="acronym">LORIA</orgName><date type="start">2012-01-01</date><desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.loria.fr</ref></desc><listRelation><relation active="#struct-300009" type="direct"></relation><relation active="#struct-413289" type="direct"></relation><relation name="UMR7503" active="#struct-441569" type="direct"></relation></listRelation></org></tutelle><tutelle active="#struct-413289" type="indirect"><org type="institution" xml:id="struct-413289" status="VALID"><idno type="IdRef">157040569</idno><idno type="IdUnivLorraine">[UL]100--</idno><orgName>Université de Lorraine</orgName><orgName type="acronym">UL</orgName><date type="start">2012-01-01</date><desc><address><addrLine>34 cours Léopold - CS 25233 - 54052 Nancy cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.univ-lorraine.fr/</ref></desc></org></tutelle><tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city">Nancy</settlement><settlement type="city">Metz</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Université de Lorraine</orgName></affiliation></author></analytic><series><title level="j">Journal of Complexity</title><idno type="ISSN">0885-064X</idno><imprint><date type="datePub">2007</date></imprint></series></biblStruct></sourceDesc></fileDesc><profileDesc><textClass><keywords scheme="mix" xml:lang="en"><term>Analog computation</term><term>Church-Turing thesis</term><term>Computable analysis</term><term>Differential equations</term><term>General Purpose Analog Computer</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">In the last decade, the field of analog computation has experienced renewed interest. In particular, there have been several attempts to understand which relations exist between the many models of analog computation. Unfortunately, most models are not equivalent. It is known that Euler's Gamma function is computable according to computable analysis, while it cannot be generated by Shannon's General Purpose Analog Computer (GPAC). This example has often been used to argue that the GPAC is less powerful than digital computation. However, as we will demonstrate, when computability with GPACs is not restricted to real-time generation of functions, we obtain two equivalent models of analog computation. Using this approach, it has been shown recently that the Gamma function becomes computable by a GPAC \cite{Gra04}. Here we extend this result by showing that, in an appropriate framework, the GPAC and computable analysis are actually equivalent from the computability point of view, at least in compact intervals. Since GPACs are equivalent to systems of polynomial differential equations then we show that all real computable functions over compact intervals can be defined by such models.</div></front></TEI><affiliations><list><country><li>France</li><li>Portugal</li></country><region><li>Grand Est</li><li>Lorraine (région)</li></region><settlement><li>Metz</li><li>Nancy</li></settlement><orgName><li>Université de Lorraine</li></orgName></list><tree><country name="France"><noRegion><name sortKey="Bournez, Olivier" sort="Bournez, Olivier" uniqKey="Bournez O" first="Olivier" last="Bournez">Olivier Bournez</name></noRegion><name sortKey="Hainry, Emmanuel" sort="Hainry, Emmanuel" uniqKey="Hainry E" first="Emmanuel" last="Hainry">Emmanuel Hainry</name></country><country name="Portugal"><noRegion><name sortKey="Campagnolo, Manuel L" sort="Campagnolo, Manuel L" uniqKey="Campagnolo M" first="Manuel L." last="Campagnolo">Manuel L. Campagnolo</name></noRegion><name sortKey="Graca, Daniel S" sort="Graca, Daniel S" uniqKey="Graca D" first="Daniel S." last="Graça">Daniel S. Graça</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 004A43 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 004A43 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Main
|étape= Exploration
|type= RBID
|clé= Hal:hal-00760984
|texte= Polynomial differential equations compute all real computable functions on computable compact intervals
}}
| This area was generated with Dilib version V0.6.33. |  |