The paper

"On the computational complexity of algebraic numbers: the Hartmanis--Stearns problem revisited"
by Boris Adamczewski, Julien Cassaigne, Marion Le Gonidec
https://arxiv.org/abs/1601.02771

claims in Theorem 2.3: " An algebraic irrational real number cannot be generated by a one-stack machine, or equivalently, by a determistic push down automaton."

I have read and checked the article, have not found any gap in it, and thus the Hartmanis-Stearns conjecture is closed by the theorem? Since the conjecture is hard to prove, I suspect that I misunderstood the article or some fault in it.

• But the Hartmanis-Stearn conjecture is about computability by a real Turing machine, not just by a (D)PDA. This paper proves a weaker form. Sep 18 '17 at 10:35

First, the name of the conjecture is "Hartmanis-Stearns", not "Hartmanis-Stearn".

Second, the Hartmanis-Stearns conjecture concerns those real numbers computable by a multi-tape Turing machine in real time; in other words, the TM must compute the n'th digit in n time.

Third, the result of Adamczewski et al. is only about finite automata and deterministic pushdown automata, both of which are weaker models than real-time Turing machines.

• Thank you for your correcting, but could you be so kind as to see rjlipton.wordpress.com/2012/06/15/… Sep 18 '17 at 12:34
• I will edit the name of the conjecture. Thank you again Sep 18 '17 at 12:36
• Nothing Lipton said invalidates my reply. Sep 18 '17 at 12:44