Is there a primitive recursive function which gives the nth digit of $\pi$, despite the table-maker's dilemma?

Question

I asked a question about this a while ago and it got deleted, so I've looked into it a bit more and I'll explain my problem better.

Planetmath.org told me that there is a primitive recursive function which gives the nth digit of $\pi$, but didn't prove it. When I asked before how one might prove it, a couple of people suggested using Gregory's series. Now I can see that if you know that to find the nth digit of $\pi$ you need to calculate it to within $10^{-m}$ where m is a p.r.f of n, you can define $$\lfloor{{10}^n\pi}\rfloor = \lfloor\frac{4\sum_{i=1}^{5\times10^{m-1}} \lfloor{\frac{10^{2m+1}}{2i-1}}\rfloor(-1)^{i-1}}{10^{2m+1-n}}\rfloor$$ and then you're basically there.

The problem is this: can you ever find an m such that calculating pi to accuracy $10^{-m}$ gives you the nth digit correct with probability 1? Isn't there always a small probability that the digits between the nth and the mth would be all 9 or all 0, and so you could still get the nth digit wrong, because say they were all 9, you could have calculated a number which had the nth digit one higher, say ...300000... instead of ...299999... which would still be accurate to within $10^{-m}$. In fact if as is suspected $\pi$ is normal, doesn't the sequence of n nines occur an infinite number of times for any n? This problem is called the table-maker's dilemma, but I haven't found it explicitly mentioned in this context.

So, my question is, is it the case that either a) you can't really define a primitive recursive function using an arithmetic series like this, or b) there is actually some way of finding m as a function of n. Thanks!

Answer 1

It was proved by K. Mahler (see also here or here for better bounds), that

$$\left|\pi - \frac{p}{q}\right| \geq q^{-42}$$

for any integers $p,q \geq 2$. Thus, there is a limit to how long the string of $9$'s or zeros can be. In other words, using the V. Kh. Salikhov's bound, any $m \geq 8n$ would suffice.

I hope this helps $\ddot\smile$

Answer 2

If we simply want the function to be computable (i.e. "recursive" in the jargon of computability theory), this is not a problem. We have a modulus of convergence for a series for $\pi$, so we know an error bound on each partial sum, with those error bounds going to zero. In effect, we have a computable sequence of nested rational intervals, whose intersection is just $\pi$.

So, if we simply compute better and better approximations, because $\pi$ is irrational we will eventually see that $\pi$ is greater than, or less than, any particular rational number $r$, because $r$ will eventually fall outside one of the intervals in our sequence.

Because finite decimal expansions give rational numbers, this means we can pin down the precise decimal expansion by repeatedly finding the next digit in this way.

However, this process is not obviously primitive recursive, because there is no bound on how small the interval will need to be before it excludes our target rational $r$. This is exactly the issue mentioned in the question, where a long string of $9$s in an approximation could eventually cause a change in a much earlier digit of the expansion. The algorithm I just mentioned uses an unbounded search to find an interval that excludes $r$, while primitive recursive methods are not generally able to perform unbounded searches.

In general, if we look at numbers other than $\pi$, it is not clear at all that we could convert an arbitrary Cauchy sequence of rationals with a given modulus of convergence into a decimal expansion via a single primitive recursive process.

So, if the decimal expansion of $\pi$ is indeed primitive recursive, some other method, or some additional (nontrivial) information about the number $\pi$ or the sequence of approximations will be necessary.