<p>The Hartmanis-Stearns Conjecture says that a number computed in real time by a Turing Machine is either rational or transcendental. We know that there is some transcendental (Liouville) number that can be computed in real time. The <a href="https://en.wikipedia.org/wiki/Bailey%E2%80%93Borwein%E2%80%93Plouffe_formula" rel="nofollow noreferrer">BBP algorithm</a> for computing $\pi$ outputs the first $n$ digits in nearly linear time ($O(n (\log n)^c)$; linear time for this being the same as real time), so it's at least plausible that $\pi$ is real-time computable.</p>

<blockquote>
  <p>Is there an algorithm outputting $e$ in  real time?</p>
</blockquote>

CC BY-SA 3.0
2017-12-27T17:10:01.367Z
I'd be curious to see the reference for $\pi$.
Joshua Grochow
CC BY-SA 3.0
2017-12-27T19:31:12.613Z
The way I understand it, the Hartmanis and Stearns conjecture that Turing machines cannot compute algebraic numbers in real time (require at least super linear time), don't think it implies all transcendental numbers can be computed in real time.
Nikhil
CC BY-SA 3.0
2017-12-27T21:44:44.947Z
Not sure if it's real time or not, but e has a very nice continued fraction as I recall. Computing that in a clever way may be a good start.
Artimis Fowl
CC BY-SA 3.0
2017-12-28T04:32:26.010Z
@Nikhil yes, you are right, but I am not sure if $e$ belongs this kind of transcendental. so...
XL _At_Here_There
CC BY-SA 3.0
2017-12-28T05:04:10.147Z
@JoshuaGrochow I have to confess that I am not sure now, but the BBP algorithm seems much faster https://en.wikipedia.org/wiki/Bailey%E2%80%93Borwein%E2%80%93Plouffe_formula Maybe I have made a mistake.
XL _At_Here_There
CC BY-SA 3.0
2017-12-28T05:06:25.060Z
@ArtimisFowl Obvious, the very nice continued fraction for $e$ is not real time or linear time, since multiplication is superlinear.
XL _At_Here_There
CC BY-SA 3.0
2017-12-28T09:03:01.940Z
@XL_at_China: I think that BBP runs in $O(n \log^3 n)$ (to compute the binary $n$-th digit of $\pi$) and in order to have real time it should be at most $O(n)$. Note that even if it is $O(n)$; to get real time from linear time the algorithm for computing the $\pi$ digits should output the whole sequence $\pi(1),...,\pi(n)$ on input $1^n$ in time $O(n)$ (see [Why The Hartmanis-Stearns Conjecture Is Still Open](https://rjlipton.wordpress.com/2012/06/15/why-the-hartmanis-stearns-conjecture-is-still-open/))
Marzio De Biasi
CC BY-SA 3.0
2017-12-28T09:26:14.270Z
@MarzioDeBiasi  BBP runs in $O(nlogn)$, see https://en.wikipedia.org/wiki/Bailey%E2%80%93Borwein%E2%80%93Plouffe_formula
XL _At_Here_There
CC BY-SA 3.0
2017-12-28T13:30:09.737Z
@XL_at_China: in the original [BBP paper](http://www.davidhbailey.com/dhbpapers/digits.pdf) they say that " ... So even with ordinary multiplication the bit complexity is $O(n \log^3(n))$ ...". Has it been improved?
Marzio De Biasi
CC BY-SA 3.0
2017-12-28T15:07:13.923Z
There indeed are Liouville numbers that are computable in real time, but why is that a consequence of the Hartmanis-Stearns conjecture?
Sasho Nikolov
CC BY-SA 3.0
2018-01-05T09:37:46.147Z
@SashoNikolov Hmm. It is easy to construct sequences of digits that are computable in real time, but not eventually periodic. Then the HS conjecture implies such numbers have to be transcendental. However, this doesn't imply they are Liouville numbers.
Emil Jeřábek
<cc.complexity-theory><reference-request><nt.number-theory><comp-number-theory>
Is there any algorithm outputing $e$ in real time?
XL _At_Here_There
# Is there any algorithm outputing $e$ in real time?

(Asked by: username_0 on 2017-12-27)

The Hartmanis-Stearns Conjecture says that a number computed in real time by a Turing Machine is either rational or transcendental. We know that there is some transcendental (Liouville) number that can be computed in real time. The [BBP algorithm](https://en.wikipedia.org/wiki/Bailey%E2%80%93Borwein%E2%80%93Plouffe_formula) for computing $\pi$ outputs the first $n$ digits in nearly linear time ($O(n (\log n)^c)$; linear time for this being the same as real time), so it's at least plausible that $\pi$ is real-time computable.

> Is there an algorithm outputting $e$ in real time?

**Tags:** cc.complexity-theory, reference-request, nt.number-theory, comp-number-theory
> **Comments:**
> **username_1**: I'd be curious to see the reference for $\pi$.  
> **username_2**: The way I understand it, the Hartmanis and Stearns conjecture that Turing machines cannot compute algebraic numbers in real time (require at least super linear time), don't think it implies all transcendental numbers can be computed in real time.  
> **username_3**: Not sure if it's real time or not, but e has a very nice continued fraction as I recall. Computing that in a clever way may be a good start.  
> **username_0**: @Nikhil yes, you are right, but I am not sure if $e$ belongs this kind of transcendental. so...  
> **username_0**: @JoshuaGrochow I have to confess that I am not sure now, but the BBP algorithm seems much faster https://en.wikipedia.org/wiki/Bailey%E2%80%93Borwein%E2%80%93Plouffe_formula Maybe I have made a mistake.  
> **username_0**: @ArtimisFowl Obvious, the very nice continued fraction for $e$ is not real time or linear time, since multiplication is superlinear.  
> **username_4**: @XL_at_China: I think that BBP runs in $O(n \log^3 n)$ (to compute the binary $n$-th digit of $\pi$) and in order to have real time it should be at most $O(n)$. Note that even if it is $O(n)$; to get real time from linear time the algorithm for computing the $\pi$ digits should output the whole sequence $\pi(1),...,\pi(n)$ on input $1^n$ in time $O(n)$ (see [Why The Hartmanis-Stearns Conjecture Is Still Open](https://rjlipton.wordpress.com/2012/06/15/why-the-hartmanis-stearns-conjecture-is-still-open/))  
> **username_0**: @MarzioDeBiasi  BBP runs in $O(nlogn)$, see https://en.wikipedia.org/wiki/Bailey%E2%80%93Borwein%E2%80%93Plouffe_formula  
> **username_4**: @XL_at_China: in the original [BBP paper](http://www.davidhbailey.com/dhbpapers/digits.pdf) they say that " ... So even with ordinary multiplication the bit complexity is $O(n \log^3(n))$ ...". Has it been improved?  
> **username_5**: There indeed are Liouville numbers that are computable in real time, but why is that a consequence of the Hartmanis-Stearns conjecture?  
> **username_6**: @SashoNikolov Hmm. It is easy to construct sequences of digits that are computable in real time, but not eventually periodic. Then the HS conjecture implies such numbers have to be transcendental. However, this doesn't imply they are Liouville numbers.  

---

## 0 answers

