Liouville Numbers and the Computational Complexity of Changing Bases
Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
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.
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 | 50-62 |
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: 250487288