# Irrationality of $\pi$ from the spigot algorithm?

The spigot algorithm for BPP formula gives hexadecimal digits of $\pi$ one at a time.

Is it possible to prove directly that this algorithm cannot be computed with bounded-memory? (From R J Lipton It seems to take $O(\log(n))$ space as an upper bound, we need a lower bound).

That would immediately imply that it wasn't periodic and hence $\pi$ is irrational.

Can this proof be done? Or maybe it depends on something difficult number theoretic result about modular exponentiation? but if it could be reduced to something like that, that would be interesting too.

-
If we can prove that a particular algorithm is "lousy," that doesn't show there can't be a good one. –  André Nicolas Feb 5 '13 at 17:18
@Amzoti, why did you delete my note about O(log(n))? –  user58512 Feb 5 '13 at 17:23
Your comment got cut off. Can it be posted again? –  André Nicolas Feb 5 '13 at 17:32
@user58512: sorry, it was accidental and not intentional. Regards –  Amzoti Feb 5 '13 at 17:52
A bit tangential but if you do not already know it this is a delightful example of a decimal spigot algorithm for $\pi$. (I'd call BBP a digit extraction algorithm instead.) –  WimC Feb 5 '13 at 20:42