Hartmanis–Stearns conjecture

An infinite word is said to be real-time computable when there exists a multitape Turing machine which (run without input) 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 ${\displaystyle n}$ in unary outputs the first ${\displaystyle n}$ letters of the word in time ${\displaystyle O(n)}$. The Hartmanis–Stearns conjecture states that if ${\displaystyle x}$ is a real number whose expansion in some base ${\displaystyle b\ge 2}$ (e.g., the decimal expansion for ${\displaystyle b=10}$) is real-time computable, then ${\displaystyle x}$ is rational or transcendental.

The conjecture has the deep implication that there is no integer multiplication algorithm in ${\displaystyle O(n)}$ (while an ${\displaystyle O(n\log (n))}$ algorithm is known).

A partial result was proved by Boris Adamczewski and Yann Bugeaud (a previous claimed proof by John H. Loxton and Alfred van der Poorten turned out to contain a gap): ${\displaystyle x}$ is rational or transcendental if the expansion of ${\displaystyle x}$ in some base ${\displaystyle b\ge 2}$ is an automatic sequence. This was subsequently generalized by Boris Adamczewski, Julien Cassaigne and Marion Le Gonidec to sequences generated by deterministic pushdown automata.