Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

On the computational complexity of algebraic numbers: the Hartmanis-Stearns problem revisited


Authors: Boris Adamczewski, Julien Cassaigne and Marion Le Gonidec
Journal: Trans. Amer. Math. Soc. 373 (2020), 3085-3115
MSC (2010): Primary 11B85, 11J81, 68Q45, 68R15, 11J87
DOI: https://doi.org/10.1090/tran/7915
Published electronically: February 20, 2020
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We consider the complexity of integer base expansions of algebraic irrational numbers from a computational point of view. A major contribution in this area is that the base-$ b$ expansion of algebraic irrational real numbers cannot be generated by finite automata. Our aim is to provide two natural generalizations of this theorem. Our main result is that the base-$ b$ expansion of algebraic irrational real numbers cannot be generated by deterministic pushdown automata. Incidentally, this completely solves the Hartmanis-Stearns problem for the class of multistack machines. We also confirm an old claim of Cobham from 1968 proving that such real numbers cannot be generated by tag machines with dilation factor larger than one. In order to stick with the modern terminology, we also show that the latter generate the same class of real numbers as morphisms with exponential growth.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 11B85, 11J81, 68Q45, 68R15, 11J87

Retrieve articles in all journals with MSC (2010): 11B85, 11J81, 68Q45, 68R15, 11J87


Additional Information

Boris Adamczewski
Affiliation: Université Lyon, Université Claude Bernard Lyon 1, CNRS UMR 5208, Institut Camille Jordan, F-69622 Villeurbanne Cedex, France
Email: Boris.Adamczewski@math.cnrs.fr

Julien Cassaigne
Affiliation: CNRS, Aix-Marseille Université, Institut de Mathématiques de Marseille, case 907, 163 avenue de Luminy, 13288 Marseille Cedex 9, France
Email: Julien.Cassaigne@math.cnrs.fr

Marion Le Gonidec
Affiliation: Université de la Réunion, Laboratoire d’Informatique et de Mathématiques, Parc technologique universitaire, 2 rue Joseph Wetzell, 97490 Sainte-Clotilde, Réunion France
Email: marion.le-gonidec@univ-reunion.fr

DOI: https://doi.org/10.1090/tran/7915
Received by editor(s): October 3, 2017
Received by editor(s) in revised form: October 31, 2018, and March 13, 2019
Published electronically: February 20, 2020
Additional Notes: This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme under the Grant Agreement No 648132.
Article copyright: © Copyright 2020 American Mathematical Society