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 theoryTemplate:R (earning them the 1993 ACM Turing Award).

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 $n$ in unary outputs the first $n$ letters of the word in time $O(n)$.Template:R The Hartmanis–Stearns conjecture states that if $x$ is a real number whose expansion in some base $b\ge 2$ (e.g., the decimal expansion for $b=10$) is real-time computable, then $x$ is rational or transcendental.Template:R

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

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