# Are there BBP formulas for all computable numbers?

A BBP algorithm is a formula with the following form where $b \in \mathbb Z$, $b \ge 2$, and $p(k)$ and $q(k)$ are polynomials in $k$ $$\sum_{k=0}^{\infty}\frac{1}{b^k}\frac{p(k)}{q(k)}$$ There are known BBP formulas for many computable numbers and it is easy to prove that any number with a BBP formula is computable.

Obviously all rationals have BBP formulas, let $n$ equal the length of the period in base $b$ and let $q(k)=1$ and $p(k) = \lfloor b^n\frac{p}{q}\rfloor$

I don't believe that there is a general form like that for all computable reals, i.e. you cannot given a definition of an irrational $\alpha$ derive $b$,$p(k)$,$q(k)$, but is it true that one exists for all computable numbers?

You can easily use diagonalization to construct a computable real which is not of this form. Fix some enumeration of all triplets $(b,p,q)$. I will describe a process that generates binary digits of a real number.
The process goes over all triplets $(b,p,q)$ in the fixed order. Suppose that it's time to handle $(b_i,p_i,q_i)$, and that currently we have generated the digits $\beta_1 \dots \beta_n$. The process evaluates the corresponding sum $S(b,p,q)$ to such a precision that the first $n+1$ binary digits can be gleaned for it. It outputs $\beta_{n+1}$ so as not to equal to $S(b,p,q)$.
• To me, your cheat seems to be that enumerating $(b,p,q)$ is not the same as enumerating the set of numbers $S(b,p,q)$. You're not making sure the "new" number is not on the list. – André Souza Lemos May 7 '15 at 1:59