4
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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)$.

The argument as stated is not 100% correct, and I'm leaving it to the reader to discover where I cheated and to fix the proof.

$\endgroup$
  • $\begingroup$ I didn't think diagonalization worked with countable sets? $\endgroup$ – ruler501 May 6 '15 at 23:02
  • $\begingroup$ On the contrary, diagonalization works only for countable sets. $\endgroup$ – Yuval Filmus May 6 '15 at 23:28
  • $\begingroup$ I thought it could only be used to prove that one set is countable and the other isn't. $\endgroup$ – ruler501 May 6 '15 at 23:40
  • $\begingroup$ No, it's a general technique which is very useful in set theory, recursion theory, complexity theory, and probably many other areas. $\endgroup$ – Yuval Filmus May 6 '15 at 23:41
  • $\begingroup$ 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. $\endgroup$ – André Souza Lemos May 7 '15 at 1:59

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.