On the Complexity of Conversion Between Classic Real Number Representations
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
It is known that while it is possible to convert between many different representations of irrational numbers (e.g., between Dedekind cuts and Cauchy sequences), it is in general not possible to do so subrecursively: conversions in general need to perform unbounded search. This raises the question of categorizing the pairs of representations between which either subrecursive conversion is possible, or is not possible. The purpose of this paper is to prove the following positive result: for a number of well-known representations (Beatty sequences, Dedekind cuts, General base expansions, Hurwitz characteristics, and Locators) conversion between the representations can be performed effectively and with good subrecursive bounds.
Original language | English |
---|---|
Title of host publication | Beyond the Horizon of Computability - 16th Conference on Computability in Europe, CiE 2020, Proceedings |
Editors | Marcella Anselmo, Gianluca Della Vedova, Florin Manea, Arno Pauly |
Publisher | Springer VS |
Publication date | 2020 |
Pages | 75-86 |
ISBN (Print) | 9783030514655 |
DOIs | |
Publication status | Published - 2020 |
Event | 16th Conference on Computability in Europe, CiE 2020 - Fisciano, Italy Duration: 29 Jun 2020 → 3 Jul 2020 |
Conference
Conference | 16th Conference on Computability in Europe, CiE 2020 |
---|---|
Land | Italy |
By | Fisciano |
Periode | 29/06/2020 → 03/07/2020 |
Series | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Volume | 12098 LNCS |
ISSN | 0302-9743 |
- Computable analysis, Computational complexity, Representation of irrational numbers, Subrecursion
Research areas
ID: 250606432