From: "Perry E. Metzger" <pmetzger@lehman.com>
Date: Mon, 24 Jan 94 20:16:43 PST
To: cypherpunks@toad.com
Subject: Re: Randomness of a bit string
In-Reply-To: <199401250337.TAA14525@mail.netcom.com>
Message-ID: <199401250411.XAA01844@snark>
MIME-Version: 1.0
Content-Type: text/plain



Timothy C. May says:
> If someone claims they can "prove" the sequence "0
> 1101100110111100010" is really random, ask them _how_. Ask them if the
> compression "Chaitin 27," meaning the example number given on page 27
> of Chaitin's book is not that same number, making it hardly random.
> 
> (Is it cheating to invoke other systems, books, etc. in the
> definition? Hardly.

Wrong, Tim. An algorithm must be self contained. If you have to refer
to Chaitin's book in the algorithm, you must include it in the
algorithm. For a proof, consider the following notion: you have a
large number that you THINK is incompressable. Write it down in the
"little book o' random numbers", now refer to it as the third number
in the book. Obviously, of course, this is bullshit -- if you
transmitted it to someone that way you would have to send the book,
too. This is unlike your earlier (correct) proof that you can't show a
number is random because where there an algorithm you could order the
random numbers and the first would no longer be random, because the
algorithm *is* self contained in that case.

> The mass of
> planet motion observation data certainly _looked_ random to ancient
> astronomers, until Kepler found his amazing compression of the data.)

Its correct that Kepler compressed the string, but incorrect to note
that having written the numbers in a book had anything to do with it.

Perry