NetNews Usenet Archive 1993 #1/NN_1993_1.iso/spool/sci/math/17647

Internet Message Format | 1993-01-04 | 3.9 KB

Path: sparky!uunet!pipex!bnr.co.uk!uknet!acorn!armltd!dseal
From: [e-mail] (David Seal)
Newsgroups: sci.math
Subject: Re: Pseudorandomness and computable numbers (was Re: Number of numbers (Was Re: PI))
Message-ID: <[e-mail]>
Date: 4 Jan 93 16:34:12 GMT
References: <[e-mail]>
Sender: [e-mail]
Distribution: sci
Organization: A.R.M. Ltd, Swaffham Bulbeck, Cambs, UK
Lines: 76

In article <[e-mail]> [e-mail] (Magnus
Olsson) writes:

>In article <[e-mail]> [e-mail] writes:
>> 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

This won't really do, assuming you want a PRDE number to contain all decimal
sequences with uniform distribution. Consider the function f which takes a
number, expresses it in binary (choosing the terminating expansion if
possible), then reads the result as a decimal number. (So f(1/2) = 1/10,
f(5/8) = 101/1000 and f(1/3) = 1/99, for instance, since 1/2, 5/8 and 1/3
expressed in binary are 0.1, 0.101 and 0.01010101... respectively.)

If we have a procedure to evaluate a number X to however many decimal digits
we want, we can use it plus ordinary decimal->binary conversion to evaluate
X to however many binary digits we want. We can therefore compute f(X) to
however many decimal digits we want. So if X is computable, so is f(X).

By a similar argument, if X is computable, so is f^(-1)(X), assuming it
exists (it won't if the decimal expansion of X contains a digit other than 0
or 1, or ends with an infinite sequence of 1s.

So f(X) is computable if and only if X is computable.

So if we have a non-computable number X, f(X) is also non-computable. But
the decimal expansion of f(X) contains only 0s and 1s: f(X) is therefore a
non-computable number which cannot reasonably be regarded as PRDE. I.e.
non-computability does not match the intuitive requirements for a definition
of a PRDE number.

>> 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.

The above shows that a non-computable number may not be PRDE. Conversely, it
is known that computable numbers can be PRDE by some definitions at least. A
reasonably well-known example is the number:

  0.1234567891011121314151617181920212223242526272829...

formed by concatenating the decimal expansions of the integers 1, 2, 3, ...

This number is obviously computable. All decimal sequences of any given
length occur with equal probability in it in the long run, and given a
section of the sequence from some unknown position, you cannot predict the
next digit with better than a 10% chance of success unless you have *some*
knowledge of where the section of the sequence came from. It might therefore
reasonably be regarded as being *provably* PRDE by some definitions.

So I don't believe non-computability and PRDE-ness have much to do with each
other.

Of course, this sequence is not a good source of pseudo-random numbers in
practice, as it contains a lot of short-term near-periodicity: basically,
although everything averages out in the long term, there are much greater
short term fluctuations than you would expect statistically. But given any
particular statistical test or set of tests that a sequence was to satisfy,
I suspect it would be reasonably easy to construct a number that was
provably both PRDE and computable.

David Seal
[e-mail]

All opinions are mine only...