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^[1] (earning them the 1993 ACM Turing Award).

Unsolved problem in computer science

If the expansion of a real ${\displaystyle x}$ in some base ${\displaystyle b\geq 2}$ is real-time computable, must ${\displaystyle x}$ be rational or transcendental?

More unsolved problems in computer science

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)}$.^[2][3] The Hartmanis–Stearns conjecture states that if ${\displaystyle x}$ is a real number whose expansion in some base ${\displaystyle b\geq 2}$ (e.g., the decimal expansion for ${\displaystyle b=10}$) is real-time computable, then ${\displaystyle x}$ is rational or transcendental.^[4][3]

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).^[3]