From: markc@smsc.sony.com (Mark Corscadden)
Subject: Re: Number of numbers (Was Re: PI)
Organization: Sony Microsystems Corp, San Jose, CA
Date: Mon, 4 Jan 93 23:27:23 GMT

In article <1992Dec31.012553.146@front.se> samuel@front.se writes:
>Definition in this posting : Computable numbers = All numbers that are the
>output of some kind of algorithm (Trancendental as well as non-trancendental,
>please note that ALL non-trancendental numbers are computable). 
>
>Example : SUM(10^-(n!)), which is a computable trancendental number.
...
>I must admit that I have become confused now. Since, as John points out, there
>exist many algorithms to determine the decimals of PI, then PI ought to
>be a computable number also ! But I have a strange (and perhaps totally
>irrelevant) gut feeling that this is NOT the case.
...
>One difference between PI and SUM(10^-(n!)) is that the decimal expansion of 
>the latter is much simplier to calculate, but this seems to be a VERY WEAK
>argument !

No one seems to have tried to find just a little kernel of truth in
Samuel's misgivings concerning the computability of PI, so here goes.
Disclaimer: I don't know a whole lot about computation theory.

Let N be the natural numbers { 0, 1, 2, ... } and for now only consider
functions from N -> N.

Aren't there several fundamental classes of computable functions F: N -> N?
Some generous expert might offer to clean up the following definitions, but
I remember three classes of functions, which I've described as well as
memory permits below:

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.

2)  ========== partial recursive functions
    Here you are allowed to have general loops with no pre-computed upper
    bound on the number of passes.  This creates the possibility that
    the program might get stuck in an infinite loop for some input values,
    so for such values the partial recursive function is undefined.
    (Technically, you either have F: S -> N where S is a subset of N, or
    you allow F: N -> N union {undefined}.)

3)  ========== total recursive functions
    This is really just a particular type of partial recursive function,
    namely one where there is no input value which actually causes the
    program to get stuck in an infinite loop.

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.

Then so far all anyone has told Samuel is that PI is a total recursive
real number, and that fails to address Samuel's concerns.

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.

For that matter, is anything known about which real numbers are total
recursive but fail to be primitive recursive?  Anyone know the standard
terminology used in this area?

Mark Corscadden
markc@smsc.sony.com
work: (408)944-4086
Newsgroups: alt.folklore.computers