On the Complexity of Conversion Between Classic Real Number Representations
Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
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.
Originalsprog | Engelsk |
---|---|
Titel | Beyond the Horizon of Computability - 16th Conference on Computability in Europe, CiE 2020, Proceedings |
Redaktører | Marcella Anselmo, Gianluca Della Vedova, Florin Manea, Arno Pauly |
Forlag | Springer VS |
Publikationsdato | 2020 |
Sider | 75-86 |
ISBN (Trykt) | 9783030514655 |
DOI | |
Status | Udgivet - 2020 |
Begivenhed | 16th Conference on Computability in Europe, CiE 2020 - Fisciano, Italien Varighed: 29 jun. 2020 → 3 jul. 2020 |
Konference
Konference | 16th Conference on Computability in Europe, CiE 2020 |
---|---|
Land | Italien |
By | Fisciano |
Periode | 29/06/2020 → 03/07/2020 |
Navn | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Vol/bind | 12098 LNCS |
ISSN | 0302-9743 |
ID: 250606432