Liouville Numbers and the Computational Complexity of Changing Bases
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
We study the computational complexity of uniformly converting the base-a expansion of an irrational numbers to the base-b expansion. In particular, we are interested in subsets of the irrationals where such conversion can be performed with little overhead. We show that such conversion is possible, essentially with polynomial overhead, for the set of irrationals that are not Liouville numbers. Furthermore, it is known that there are irrational numbers x such that the expansion of x in one integer base is efficiently computable, but the expansion of x in certain other integer bases is not. We prove that any such number must be a Liouville number.
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 | 50-62 |
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 |
- Computability, Computational complexity, Diophantine approximation, Number theory
Research areas
ID: 250487288