Hartmanis–Stearns conjecture

Short description: Open problem in computer science

Unsolved problem in computer science: If the expansion of a real $x$ in some base $b\ge 2$ is real-time computable, must $x$ be rational or transcendental? (more unsolved problems in computer science)

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$ in unary outputs the first $n$ letters of the word in time $O(n)$. 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.

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).

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$ 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 Gonidec to sequences generated by deterministic pushdown automata.