Hartmanis–Stearns conjecture

In theoretical computer science and mathematics, the Hartmanis–Stearns conjecture is an open problem named after Juris Hartmanis and Richard E. Stearns, who posed it in a 1965 paper that founded the field of computational complexity theory.
An infinite word is said to be real-time computable when there exists a multitape Turing machine which writes the successive letters of the word on its output tape, taking a bounded amount of time between two successive letters. Equivalently, there exists a multitape Turing machine which given a natural number in unary outputs the first letters of the word in time. The Hartmanis–Stearns conjecture states that if is a real number whose expansion in some base is real-time computable, then is rational or transcendental.
The conjecture has the deep implication that there is no integer multiplication algorithm in .
A partial result was proved by Boris Adamczewski and Yann Bugeaud : is rational or transcendental if the expansion of in some base is an automatic sequence. This was subsequently generalized by Boris Adamczewski, Julien Cassaigne and Marion Le Gonidec to sequences generated by deterministic pushdown automata.