4
$\begingroup$

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.

$\endgroup$
1
  • 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
    Commented Sep 18, 2017 at 10:35

1 Answer 1

18
$\begingroup$

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.

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

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.