On the computational complexity of algebraic numbers: the Hartmanis–Stearns problem revisited
Boris Adamczewski, Julien Cassaigne, Marion Le Gonidec · Transactions of the American Mathematical Society · 2019
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.