On the Complexity of Conversion Between Classic Real Number Representations

Publikation: Bidrag til bog/antologi/rapportKonferencebidrag i proceedingsForskningfagfæ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.

OriginalsprogEngelsk
TitelBeyond the Horizon of Computability - 16th Conference on Computability in Europe, CiE 2020, Proceedings
RedaktørerMarcella Anselmo, Gianluca Della Vedova, Florin Manea, Arno Pauly
ForlagSpringer VS
Publikationsdato2020
Sider75-86
ISBN (Trykt)9783030514655
DOI
StatusUdgivet - 2020
Begivenhed16th Conference on Computability in Europe, CiE 2020 - Fisciano, Italien
Varighed: 29 jun. 20203 jul. 2020

Konference

Konference16th Conference on Computability in Europe, CiE 2020
LandItalien
ByFisciano
Periode29/06/202003/07/2020
NavnLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Vol/bind12098 LNCS
ISSN0302-9743

ID: 250606432