Hartmanis–Stearns conjecture
If a machine can print the digits of a real number in real time, must that number be rational or transcendental?
Summary
Why it is open
In their 1965 paper Hartmanis and Stearns classified sequences by how fast a multitape Turing machine can print their terms: a sequence is T-computable if a machine computes its nth term within T(n) operations [1]. Numbers whose first n binary digits can be produced in O(n) operations, at most a constant multiple of n, are computable in real time [5]. Rational numbers have this property [5], and so do some transcendental (non-algebraic) numbers, such as the sum of 2^(−n!) over n ≥ 1 [8, 9]. At the end of their paper Hartmanis and Stearns asked whether there are irrational algebraic numbers, real solutions of polynomials with integer coefficients, whose first n binary digits can be computed in O(n) operations [8, 9]. Boris Adamczewski and Yann Bugeaud write that a negative answer is expected [5]; the Hartmanis–Stearns conjecture is that no irrational algebraic number is computable in real time by a Turing machine [8].
Patrick Fischer, Albert Meyer and Arnold Rosenberg proved in 1970 that real-time computability on a Turing machine is equivalent to linear-time computability, so the conjecture can be read as a statement about linear time [3, 8]. Xiang Huang and colleagues add that linear time depends strongly on the model of computation, so that the conjecture as stated is specific to Turing machines [8].
Adamczewski, Julien Cassaigne and Marion Le Gonidec give two reasons why the problem is hard [9]. Known fast methods for the digits of algebraic irrational numbers rest on the cost of multiplying two n-digit numbers, which is quasilinear, and whether it can be done in linear time "remains a famous open problem" [9]. R. P. Brent showed that the digits of √2 can be computed in linear time if integers can be multiplied in linear time [8], and a 2012 post on the blog Gödel's Lost Letter and P=NP concludes that the conjecture implies that multiplication takes more than linear time, a lower bound it calls "wide open" [6]. In the other direction, a negative answer would include transcendence results: the transcendence of the real-time computable number Σ 2^(−n²) was proved only in 1996, using deep work of Yu. V. Nesterenko, and that of Σ 2^(−n³) was still unknown when Adamczewski and colleagues wrote [9].
A resolution would be a proof that no irrational algebraic number is computable in real time on a multitape Turing machine, or such a machine for one of them. No prize or committee sets further terms; the status here follows Wikipedia's list of unsolved problems in computer science [11].
What is known
Restricted machines (1968–1988). In 1968 Alan Cobham proposed restricting the problem to particular classes of Turing machines, first finite automata [5, 7]. In a paper on tag machines he called a real number regular if, in some base, the positions of each digit form sets of numbers recognisable by a finite automaton; he characterised such expansions as outputs that certain tag machines generate in real time, and stated that no regular real number is algebraic irrational, using functional equations that describe the machines [2]. Cobham stated his two main theorems without proof [9]. J. H. Loxton and A. J. van der Poorten claimed in 1988 to have solved the finite-automaton case completely by a method of Mahler, but their proof "contains unfortunately a rather serious gap, as explained by" P. G. Becker [5].
Automatic numbers (2004–2017). A number is automatic if the nth digit of its expansion is the output of a finite automaton that reads the digits of n [9]. In 2004 Adamczewski, Bugeaud and Florian Luca proved that the base-b expansion of an irrational algebraic number cannot be generated by a finite automaton [4]; in their 2007 paper Adamczewski and Bugeaud state the result as "irrational automatic numbers are transcendental" [5]. The main theorem of the 2007 paper is stronger: if p(n) counts the distinct blocks of n consecutive digits in the expansion of an irrational algebraic number, then p(n)/n tends to infinity [5, 9]. They also proved that binary irrational algebraic numbers cannot be generated by a morphism, a rule that replaces each digit by a block of digits and is iterated, and that in bases b ≥ 3 they cannot be generated by a recurrent morphism [5]. Their tool was a new combinatorial transcendence criterion derived from the Schmidt subspace theorem [5], and Adamczewski, Cassaigne and Le Gonidec call the finite-automaton result "the main contribution up to date toward a negative solution" [9]. In 2017 Adamczewski and Colin Faverjon, refining a 2015 theorem of P. Philippon, proved that the value of a Mahler function (a power series satisfying a certain kind of linear functional equation) at an algebraic point inside the unit disc, other than a pole, is either transcendental or lies in the number field generated by the point and the coefficients [7]. Cobham had shown that sequences generated by finite automata give Mahler functions, and the theorem supplies, almost fifty years later, a proof of a statement he had made without proof [7].
Pushdown automata and morphisms (2020). Adamczewski, Cassaigne and Le Gonidec proved that the base-b expansion of an algebraic irrational number cannot be generated by a deterministic pushdown automaton, a finite automaton with a possibly infinite memory organised as a stack [9]. They also confirmed Cobham's second claim, that such an expansion cannot be generated by a morphism with exponential growth, a statement that also appears in Julien Albert's 2006 thesis [9]. A machine with no stack is a finite automaton, one stack gives a pushdown automaton, and two stacks already give the power of a general Turing machine, which can generate any algebraic number; the authors therefore describe their results as a complete picture of the problem for multistack machines [9]. A further criterion in their paper (Proposition 5.7) proves the transcendence of some numbers generated by more powerful machines, such as a number generated by a linear bounded automaton [9].
Analog models (2019). Huang, Titus Klinge, James Lathrop, Xiaoyuan Li and Jack Lutz showed that every algebraic number, and some transcendental numbers, can be computed in real time by deterministic chemical reaction networks, in a sense in which a concentration must be within 2^(−t) of the number at every time t ≥ 1 [8]. They describe this as a counterpoint to the conjecture, not a disproof of it [8].
Main approaches
Transcendence from digit patterns. Apply a combinatorial transcendence criterion, derived from the subspace theorem, to the digit sequences that restricted machines produce [5, 9]. Strongest evidence: finite automata, binary morphisms, deterministic pushdown automata and morphisms with exponential growth [5, 9]. Main difficulty: in 2007 Adamczewski and Bugeaud could not show that ternary algebraic numbers cannot be generated by a morphism [5]; and counting digit blocks is not enough beyond finite automata, since pushdown automata can produce sequences whose block counts grow at least like any fixed power of n [9].
Mahler's method. Describe the machine's output by functional equations and use the transcendence theory of their solutions, as Cobham proposed [2, 7]. Strongest evidence: the general dichotomy of Adamczewski and Faverjon [7]. Main difficulty: the 1988 attempt by this route had a serious gap [5], and the 2017 theorem concerns Mahler functions, which Cobham connected with finite automata; its authors describe the Hartmanis–Stearns problem itself as still largely open [7].
Restricting memory instead of time. Ask which ways of organising a machine's memory can produce algebraic irrational numbers [9]. Strongest evidence: the complete answer for multistack machines and the criterion of Proposition 5.7 [9]. Main difficulty: with two stacks a machine has the power of a general Turing machine and can generate any algebraic number [9].
Fast algorithms. Look for a way to compute the digits of an algebraic irrational number fast enough to answer the question positively; known methods go through multiplication [8, 9]. Strongest evidence: Brent's reduction from √2 to multiplication [8], and the algorithm of David Harvey and Joris van der Hoeven, published in 2021, that multiplies two n-bit integers in O(n log n) bit operations on a multitape Turing machine [10]. Main difficulty: linear-time multiplication is an open problem [9].
Open sub-questions
- The cube exponent. Is Σ 2^(−n³), which is computable in real time, transcendental, as a negative answer to the problem requires [9]?
- Ternary morphisms. Are ternary numbers generated by morphisms that are neither recurrent nor of exponential growth always rational or transcendental, as the widely believed conjecture that irrational morphic numbers are transcendental predicts [5, 9]?
- Beyond pushdown automata. For which classes of one-way machines with irrevocable output is the configuration equivalence of Proposition 5.7 always nontrivial, so that they cannot generate algebraic irrational numbers [9]?
- Analog digits. Can chemical reaction networks in the model of Huang and colleagues produce in linear time the individual digits of each number that they compute in real time [8]?
- Model dependence. Is there a reasonable discrete model of computation in which some algebraic irrational number is computable in linear time [8]?
Work on this in Papex
If you have a testable answer to one of the sub-questions above, you can draft it as a private hypothesis in Papex, or prepare the draft from Claude or ChatGPT with the Papex connector. You review the exact version, sign it and decide whether to publish it; a public record that names this problem is listed on this page. A Papex record shows who signed which version and when. It is not peer review and does not mean the hypothesis is correct.
Key references
- Hartmanis, J. & Stearns, R. E. (1965). On the computational complexity of algorithms. Transactions of the American Mathematical Society 117, 285–306. 10.1090/S0002-9947-1965-0170805-7 · Checked 16 Oct 2026
- Cobham, A. (1968). On the Hartmanis–Stearns problem for a class of tag machines. In 9th Annual Symposium on Switching and Automata Theory (SWAT 1968), 51–60. 10.1109/SWAT.1968.20 · Checked 16 Oct 2026
- Fischer, P. C., Meyer, A. R. & Rosenberg, A. L. (1970). Time-restricted sequence generation. Journal of Computer and System Sciences 4(1), 50–73. 10.1016/S0022-0000(70)80012-5 · Checked 16 Oct 2026
- Adamczewski, B., Bugeaud, Y. & Luca, F. (2004). Sur la complexité des nombres algébriques. Comptes Rendus Mathématique 339(1), 11–14. 10.1016/j.crma.2004.04.012 · Checked 16 Oct 2026
- Adamczewski, B. & Bugeaud, Y. (2007). On the complexity of algebraic numbers I. Expansions in integer bases. Annals of Mathematics 165(2), 547–565. 10.4007/annals.2007.165.547 · Checked 16 Oct 2026
- Lipton, R. J. (2012). Why the Hartmanis–Stearns conjecture is still open. Blog post on Gödel's Lost Letter and P=NP, 15 June 2012. Source · Checked 16 Oct 2026
- Adamczewski, B. & Faverjon, C. (2017). Méthode de Mahler : relations linéaires, transcendance et applications aux nombres automatiques. Proceedings of the London Mathematical Society 115(1), 55–90. 10.1112/plms.12038 · Checked 16 Oct 2026
- Huang, X., Klinge, T. H., Lathrop, J. I., Li, X. & Lutz, J. H. (2019). Real-time computability of real numbers by chemical reaction networks. Natural Computing 18(1), 63–73; published online 2018. 10.1007/s11047-018-9706-x · Checked 16 Oct 2026
- Adamczewski, B., Cassaigne, J. & Le Gonidec, M. (2020). On the computational complexity of algebraic numbers: the Hartmanis–Stearns problem revisited. Transactions of the American Mathematical Society 373(5), 3085–3115. 10.1090/tran/7915 · Checked 16 Oct 2026
- Harvey, D. & van der Hoeven, J. (2021). Integer multiplication in time O(n log n). Annals of Mathematics 193(2), 563–617. 10.4007/annals.2021.193.2.4 · Checked 16 Oct 2026
- Wikipedia. List of unsolved problems in computer science (revision of 15 September 2026). Source · Checked 16 Oct 2026
Source
Open, as listed by Wikipedia · Unsolved problems in computer science. Checked 08 Oct 2026.
The status is the source’s. Papex does not decide whether a problem is solved.
Records on this problem
No public record addresses this problem yet.