From: Eli Brandt <ebrandt@jarthur.Claremont.EDU>
Date: Mon, 24 Jan 94 22:46:45 PST
To: cypherpunks list <cypherpunks@toad.com>
Subject: Re: Randomness of a bit string
In-Reply-To: <199401250337.TAA14525@mail.netcom.com>
Message-ID: <9401250636.AA02196@toad.com>
MIME-Version: 1.0
Content-Type: text/plain


> From: tcmay@netcom.com (Timothy C. May)
> I don't believe this is overstating the case at all. To quote Gregory
> Chaitin, from a context I cannot do justice here: "...leads to the
> demonstration that a specific number cannot be proved random."

Perhaps the context is relevant.  Chaitin's `omega', for example, is
Kolmogorov random (too bad!).  (Omega is the sum over all x of m(x),
where m(x) is the Solomonoff-Levin distribution.)

> To see this another way, suppose an algorithm existed to always know
> if a given number is "random" or not. Then application of this
> algorithm to the natural numbers would presumably find the "smallest
> random number," such as "729." (An inside joke.) But this smallest
> random number would itself be intensely interesting and hardly random.

This is an informal argument, using an informal definition of
randomness.  Presumably in this discussion we could standardize
on Kolmogorov randomness, to which definition Berry's paradox
does not apply.

> --Tim May

   Eli   ebrandt@jarthur.claremont.edu