<p>First, the name of the conjecture is "Hartmanis-Stearns", not "Hartmanis-Stearn".</p>

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

<p>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.</p>

CC BY-SA 3.0
2017-09-18T12:34:57.790Z
Thank you for your correcting, but could you be so kind as to see https://rjlipton.wordpress.com/2012/06/15/why-the-hartmanis-stearns-conjecture-is-still-open/
XL _At_Here_There
CC BY-SA 3.0
2017-09-18T12:36:05.000Z
I will edit the name of the conjecture. Thank you again
XL _At_Here_There
CC BY-SA 3.0
2017-09-18T12:44:07.020Z
Nothing Lipton said invalidates my reply.
Jeffrey Shallit
CC BY-SA 3.0
2017-09-18T10:41:36.163Z
2017-09-18T10:41:36.163Z
Jeffrey Shallit
<p>The paper  </p>

<blockquote>
  <p>"On the computational complexity of algebraic numbers: the Hartmanis--Stearns problem revisited"<br>
  by Boris Adamczewski, Julien Cassaigne, Marion Le Gonidec<br>
  <a href="https://arxiv.org/abs/1601.02771" rel="nofollow noreferrer">https://arxiv.org/abs/1601.02771</a></p>
</blockquote>

<p>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."</p>

<p>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.</p>

CC BY-SA 3.0
2017-09-18T10:35:28.283Z
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.
Lamine
<cc.complexity-theory><co.combinatorics><computability><automata-theory><nt.number-theory>
Is Hartmanis-Stearns conjecture settled by this article?
XL _At_Here_There
# Is Hartmanis-Stearns conjecture settled by this article?

(Asked by: username_0 on 2017-09-18)

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.

**Tags:** cc.complexity-theory, co.combinatorics, computability, automata-theory, nt.number-theory
> **Comments:**
> **username_1**: 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.  

---

## 1 answers

### Answer by username_2 on 2017-09-18. Score: 18 | Accepted answer

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.

> **Comments:**
> **username_0**: Thank you for your correcting, but could you be so kind as to see https://rjlipton.wordpress.com/2012/06/15/why-the-hartmanis-stearns-conjecture-is-still-open/  
> **username_0**: I will edit the name of the conjecture. Thank you again  
> **username_2**: Nothing Lipton said invalidates my reply.  

---

