From: hrubin@pop.stat.purdue.edu (Herman Rubin)
Subject: Re: Number of numbers (Was Re: PI)
Organization: Purdue University Statistics Department
Date: Wed, 6 Jan 1993 22:04:38 GMT

In article <1993Jan5.200016.19037@husc3.harvard.edu> wald2@husc10.harvard.edu (Kevin Wald) writes:
>In article <1993Jan5.192626.10661@oracle.us.oracle.com> mfriedma@uucp (Michael Friedman) writes:
>>In article <1993Jan5.020509.18268@infodev.cam.ac.uk> gjm11@cus.cam.ac.uk (G.J. McCaughan) writes:
>>>In article <1993Jan4.232723.3685@smsc.sony.com> markc@smsc.sony.com (Mark Corscadden) writes:
>>>>1)  ========== primitive recursive functions
>>>>    The are the functions which you can compute in a typical general-
>>>>    purpose computer language, except that before you enter any loop
>>>>    you must first compute an upper bound on the maximum number of
>>>>    times you will be allowed to pass through the loop, and must not
>>>>    exceed this pre-computed upper bound.

>>>  [description of "partial recursive", "total recursive"]

>>>>Suppose you define a real number to be "primitive recursive" if there is
>>>>a primitive recursive function which computes the Nth decimal digit as
>>>>a function of N.  Same for a "total recursive" real number.

>>>>Does anyone know whether PI is primitive recursive by the definition above?
>>>>If not, this fact seems to capture a bit of Samuel's "gut feeling" that
>>>>his example SUM(10^-(n!)) is "much simplier to calculate" than PI, since
>>>>SUM(10^-(n!)) is clearly primitive recursive.

>>>Sorry; pi is primitive recursive. Take any of the squillions of formulas
>>>for pi which give error terms which actually give bounds on how far wrong
>>>a given approximation is. (For instance, though I wouldn't dream of
>>>actually computing pi with this, pi=4(1-1/3+1/5-1/7+1/9...) where the
>>>error incurred by stopping at any given point is at most equal to the
>>>size of the next term.) Then compute how many terms you need to take to
>>>get the first N decimal places, and what sort of precision you need to
>>>use; and run the algorithm that far. No unbounded loops in sight.

>>Is this really true?  After all, we know that there are arbitrarily
>>long strings of consecutive 0s and 9s in the decimal expansion of PI.
>>What precision to I need to compute the Nth digit of PI if that Nth
>>digit is at teh beginning of such a sequence?  After all, you can
>>change the value of digit N by adding (for 9s) or subtracting (for 0s)
>>and arbitrarily small value if the string of identical digits is long
>>enough.




>I seem to recall that there is a result about how closely pi can be
>approximated by a rational, that in particular allows you to derive
>a very simple (and definitely primitive recursive) function f(n) such
>that for any n, there cannot be more than f(n) consecutive zeros
>or nines immediately following the nth digit of pi (because otherwise the
>result of rounding pi to its nth digit would constitute a rational
>approximation closer than my ill-remembered theorem allows). Does anyone
>recall this result, and if so, can they post what it actually says?

There is a paper by Baker (sorry, I do not have the precise reference)
which I have looked at which states that |pi - p/q| > q^k, where k is
a negative number whose magnitude is less than 40.  This means that
pi is primitive recursive, since the n-th digit can be computed exactly
by computing pi to 40n digit accuracy, and also puts a limit on the 
number of 0's or 9's following the n-th digit.  However, this is not
that surprising; more than 98/99 of the numbers between 0 and 1
(Lebesgue measure) have the property that the number of 9's following
the n-th digit is less than 2n for all n, so it would not be an 
argument against the "randomness" of pi.  Even the proportion of
numbers between 0 and 1 which satisfy |x - p/q| > q^k for all q
is positive if k > 4, and I am not sure about smaller k's > 2.
-- 
Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907-1399
Phone: (317)494-6054
hrubin@snap.stat.purdue.edu (Internet, bitnet)  
{purdue,pur-ee}!snap.stat!hrubin(UUCP)