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 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?

  • 7
    $\begingroup$ I'd be curious to see the reference for $\pi$. $\endgroup$ Commented Dec 27, 2017 at 17:10
  • 2
    $\begingroup$ 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. $\endgroup$
    – Nikhil
    Commented Dec 27, 2017 at 19:31
  • 1
    $\begingroup$ @JoshuaGrochow I have to confess that I am not sure now, but the BBP algorithm seems much faster en.wikipedia.org/wiki/… Maybe I have made a mistake. $\endgroup$ Commented Dec 28, 2017 at 5:04
  • 4
    $\begingroup$ @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) $\endgroup$ Commented Dec 28, 2017 at 9:03
  • 3
    $\begingroup$ @XL_at_China: in the original BBP paper they say that " ... So even with ordinary multiplication the bit complexity is $O(n \log^3(n))$ ...". Has it been improved? $\endgroup$ Commented Dec 28, 2017 at 13:30


Your Answer

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