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 (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 {\displaystyle n} in unary outputs the first n {\displaystyle n} letters of the word in time O ( n ) {\displaystyle O(n)} . The Hartmanis–Stearns conjecture states that if x {\displaystyle x} is a real number whose expansion in some base b ≥ 2 {\displaystyle b\geq 2} (e.g., the decimal expansion for b = 10 {\displaystyle b=10} ) is real-time computable, then x {\displaystyle x} is rational or transcendental. The conjecture has the deep implication that there is no integer multiplication algorithm in O ( n ) {\displaystyle O(n)} (while an O ( n log ( n ) ) {\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): x {\displaystyle x} is rational or transcendental if the expansion of x {\displaystyle x} in some base b ≥ 2 {\displaystyle b\geq 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.
References