World's most popular travel blog for travel bloggers.

[Answers] Are there BBP formulas for all computable numbers?

, , No Comments
Problem Detail: 

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?

Asked By : ruler501

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/42233

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback