From: wald2@husc10.harvard.edu (Kevin Wald)
Newsgroups: alt.folklore.computers,sci.math
Subject: Re: Number of numbers (Was Re: PI)
Date: 6 Jan 93 01:00:15 GMT
Article-I.D.: husc3.1993Jan5.200016.19037
Organization: Harvard University Science Center

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 am not an official Oracle spokesman.  I speak for myself and no one else.

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?

Anyway, if this result isn't a figment of my imagination, then we can
at last say that the-nth-digit-of-pi is indeed a primitive recursive
function, since to find the nth digit of pi, we need only evaluate, say,
the first 10^(n+f(n)+2) (that oughta do it) terms of the Indescribably
Slow Series (tm) for pi (i.e. 4/1 - 4/3 + 4/5 . . .), so we don't
need any unbounded loops.

Kevin
wald2@husc.harvard.edu
Newsgroups: alt.folklore.computers