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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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