On the extension of computable real functions
International audience We investigate interrelationships among different notions from mathematical analysis, effective topology, and classical computability theory. Our main object of study is the class of computable functions defined over an interval with the boundary being a left-c.e. real number....
Main Authors: | , |
---|---|
Other Authors: | , , , , , , , |
Format: | Conference Object |
Language: | English |
Published: |
HAL CCSD
2017
|
Subjects: | |
Online Access: | https://hal.inria.fr/hal-01494332 https://hal.inria.fr/hal-01494332/document https://hal.inria.fr/hal-01494332/file/corrected.pdf |
id |
ftccsdartic:oai:HAL:hal-01494332v1 |
---|---|
record_format |
openpolar |
spelling |
ftccsdartic:oai:HAL:hal-01494332v1 2023-05-15T16:50:10+02:00 On the extension of computable real functions Hoyrup, Mathieu Gomaa, Walid Theoretical adverse computations, and safety (CARTE) Department of Formal Methods (LORIA - FM) Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA) Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA) Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Inria Nancy - Grand Est Institut National de Recherche en Informatique et en Automatique (Inria) Faculty of Engineering (Alex-Eng) Alexandria University Alexandrie Reykjavik, Iceland 2017-06-20 https://hal.inria.fr/hal-01494332 https://hal.inria.fr/hal-01494332/document https://hal.inria.fr/hal-01494332/file/corrected.pdf en eng HAL CCSD hal-01494332 https://hal.inria.fr/hal-01494332 https://hal.inria.fr/hal-01494332/document https://hal.inria.fr/hal-01494332/file/corrected.pdf info:eu-repo/semantics/OpenAccess Logic In Computer Science (LICS) https://hal.inria.fr/hal-01494332 Logic In Computer Science (LICS), Jun 2017, Reykjavik, Iceland http://lics.rwth-aachen.de/lics17/ Computable Analysis Left-c.e. real number Simple left-c.e. real number Generic real number Computable linear ordering Computable real function ACM: F.: Theory of Computation/F.1: COMPUTATION BY ABSTRACT DEVICES/F.1.1: Models of Computation/F.1.1.2: Computability theory ACM: F.: Theory of Computation/F.4: MATHEMATICAL LOGIC AND FORMAL LANGUAGES/F.4.1: Mathematical Logic/F.4.1.0: Computability theory [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO] info:eu-repo/semantics/conferenceObject Conference papers 2017 ftccsdartic 2021-11-07T03:57:13Z International audience We investigate interrelationships among different notions from mathematical analysis, effective topology, and classical computability theory. Our main object of study is the class of computable functions defined over an interval with the boundary being a left-c.e. real number. We investigate necessary and sufficient conditions under which such functions can be computably extended. It turns out that this depends on the behavior of the function near the boundary as well as on the class of left-c.e. real numbers to which the boundary belongs, that is, how it can be constructed. Of particular interest a class of functions is investigated: sawtooth functions constructed from computable enumerations of c.e. sets. Conference Object Iceland Archive ouverte HAL (Hyper Article en Ligne, CCSD - Centre pour la Communication Scientifique Directe) |
institution |
Open Polar |
collection |
Archive ouverte HAL (Hyper Article en Ligne, CCSD - Centre pour la Communication Scientifique Directe) |
op_collection_id |
ftccsdartic |
language |
English |
topic |
Computable Analysis Left-c.e. real number Simple left-c.e. real number Generic real number Computable linear ordering Computable real function ACM: F.: Theory of Computation/F.1: COMPUTATION BY ABSTRACT DEVICES/F.1.1: Models of Computation/F.1.1.2: Computability theory ACM: F.: Theory of Computation/F.4: MATHEMATICAL LOGIC AND FORMAL LANGUAGES/F.4.1: Mathematical Logic/F.4.1.0: Computability theory [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO] |
spellingShingle |
Computable Analysis Left-c.e. real number Simple left-c.e. real number Generic real number Computable linear ordering Computable real function ACM: F.: Theory of Computation/F.1: COMPUTATION BY ABSTRACT DEVICES/F.1.1: Models of Computation/F.1.1.2: Computability theory ACM: F.: Theory of Computation/F.4: MATHEMATICAL LOGIC AND FORMAL LANGUAGES/F.4.1: Mathematical Logic/F.4.1.0: Computability theory [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO] Hoyrup, Mathieu Gomaa, Walid On the extension of computable real functions |
topic_facet |
Computable Analysis Left-c.e. real number Simple left-c.e. real number Generic real number Computable linear ordering Computable real function ACM: F.: Theory of Computation/F.1: COMPUTATION BY ABSTRACT DEVICES/F.1.1: Models of Computation/F.1.1.2: Computability theory ACM: F.: Theory of Computation/F.4: MATHEMATICAL LOGIC AND FORMAL LANGUAGES/F.4.1: Mathematical Logic/F.4.1.0: Computability theory [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO] |
description |
International audience We investigate interrelationships among different notions from mathematical analysis, effective topology, and classical computability theory. Our main object of study is the class of computable functions defined over an interval with the boundary being a left-c.e. real number. We investigate necessary and sufficient conditions under which such functions can be computably extended. It turns out that this depends on the behavior of the function near the boundary as well as on the class of left-c.e. real numbers to which the boundary belongs, that is, how it can be constructed. Of particular interest a class of functions is investigated: sawtooth functions constructed from computable enumerations of c.e. sets. |
author2 |
Theoretical adverse computations, and safety (CARTE) Department of Formal Methods (LORIA - FM) Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA) Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA) Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Inria Nancy - Grand Est Institut National de Recherche en Informatique et en Automatique (Inria) Faculty of Engineering (Alex-Eng) Alexandria University Alexandrie |
format |
Conference Object |
author |
Hoyrup, Mathieu Gomaa, Walid |
author_facet |
Hoyrup, Mathieu Gomaa, Walid |
author_sort |
Hoyrup, Mathieu |
title |
On the extension of computable real functions |
title_short |
On the extension of computable real functions |
title_full |
On the extension of computable real functions |
title_fullStr |
On the extension of computable real functions |
title_full_unstemmed |
On the extension of computable real functions |
title_sort |
on the extension of computable real functions |
publisher |
HAL CCSD |
publishDate |
2017 |
url |
https://hal.inria.fr/hal-01494332 https://hal.inria.fr/hal-01494332/document https://hal.inria.fr/hal-01494332/file/corrected.pdf |
op_coverage |
Reykjavik, Iceland |
genre |
Iceland |
genre_facet |
Iceland |
op_source |
Logic In Computer Science (LICS) https://hal.inria.fr/hal-01494332 Logic In Computer Science (LICS), Jun 2017, Reykjavik, Iceland http://lics.rwth-aachen.de/lics17/ |
op_relation |
hal-01494332 https://hal.inria.fr/hal-01494332 https://hal.inria.fr/hal-01494332/document https://hal.inria.fr/hal-01494332/file/corrected.pdf |
op_rights |
info:eu-repo/semantics/OpenAccess |
_version_ |
1766040341018836992 |