On the Complexity of Conversion Between Classic Real Number Representations

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-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 languageEnglish
Title of host publicationBeyond the Horizon of Computability - 16th Conference on Computability in Europe, CiE 2020, Proceedings
EditorsMarcella Anselmo, Gianluca Della Vedova, Florin Manea, Arno Pauly
PublisherSpringer VS
Publication date2020
Pages75-86
ISBN (Print)9783030514655
DOIs
Publication statusPublished - 2020
Event16th Conference on Computability in Europe, CiE 2020 - Fisciano, Italy
Duration: 29 Jun 20203 Jul 2020

Conference

Conference16th Conference on Computability in Europe, CiE 2020
LandItaly
ByFisciano
Periode29/06/202003/07/2020
SeriesLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12098 LNCS
ISSN0302-9743

    Research areas

  • Computable analysis, Computational complexity, Representation of irrational numbers, Subrecursion

ID: 250606432