The paper

"On the computational complexity of algebraic numbers: the Hartmanis--Stearns problem revisited"
by Boris Adamczewski, Julien Cassaigne, Marion Le Gonidec

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.

  • 7
    $\begingroup$ 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. $\endgroup$
    – Lamine
    Sep 18, 2017 at 10:35

1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.