From: magnus@thep.lu.se (Magnus Olsson)
Newsgroups: alt.folklore.computers,sci.math
Subject: Pseudorandomness and computable numbers (was Re: Number of numbers (Was Re: PI))
Date: 2 Jan 93 09:45:03 GMT
Organization: Theoretical Physics, Lund University, Sweden

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.

This is the usual definition, with one modification: Since an algorithm
by the usual definition of algorithm must terminate, one should really
define a computable number as

# A number x is computable if and only if for each positive integer N 
# there exists an algorithm that outputs the N first decimals of x.

>In article <...>, john@gu.uwa.edu.au (John West) writes :
>>The decimals in PI *do* appear in a highly systematic and predictable fashion.
>>There are many algorithms for predicting what the next one will be.
>
>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. What do you say, Magnus ? 

I say that yes, you are confused :-)

See below for more details...

>My questions to any math guru out there are the following :
> 1. Is PI a computable number ?

Yes, of course, since there are algorithms for computing it to any
desired precision.

> 2. If the answer to (1) is NO, then why isn't it ?
> 3. Does there exist a strict definition for numbers with "pseudo-random 
>    decimal expansion" ? (I will call them PRDE-numbers)

There are actually several definitions, depending on the context. 

One rigorous definition is

# A number is a PRDE number if and only if it is not computable 

As John points out, pi isn't random according to this definition.

An operational definition is

# A number is a PRDE number if and only if, given the first N decimals
# of its expansion, one cannot predict the following M decimals with 
# <insert your favourite statistical method here>.

It's according to this latter definition (or calss of definitions)
that pi is "random". 

Note that this latter definition is of great practical importance,
since this is the basis for methods to test random-number generators. 

> 4. What is the relation(s) between computable/non-computable numbers vs 
>    PRDE/Non-PRDE numbers ? E.g. one such relation may be "A non-computable
>    number is always also a PRDE-number".

Of course this depends on the definition used for PRDE numbers. But
it seems as if there exist computable numbers that are PRDE numbers by
the second definition. I don't know if any computable number has been
*proved* to be PRDE, though.

              Magnus Olsson                | \e+      /_
    Department of Theoretical Physics      |  \  Z   / q
        University of Lund, Sweden         |   >----<           
 magnus@thep.lu.se, thepmo@seldc52.bitnet  |  /      \===== g
PGP key available via finger or on request | /e-      \q