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

Boris Adamczewski, Julien Cassaigne, Marion Le Gonidec

We consider the complexity of integer base expansions of algebraic irrational numbers from a computational point of view. We show that the Hartmanis--Stearns problem can be solved…