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$ Dec 27 '17 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
    Dec 27 '17 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$ Dec 28 '17 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$ Dec 28 '17 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$ Dec 28 '17 at 13:30

Your Answer

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

Browse other questions tagged or ask your own question.