From: kevin@axon.cs.byu.edu (Kevin Vanhorn)
Date: Mon, 24 Jan 94 12:16:43 PST
To: cypherpunks@toad.com
Subject: Randomness of a bit string
In-Reply-To: <199401241857.KAA06412@mail.netcom.com>
Message-ID: <9401242012.AA29021@axon.cs.byu.edu>
MIME-Version: 1.0
Content-Type: text/plain


Tim May writes:

> A fascinating discovery by Chaitin and others (Kolmogorov, Solomnoff,
> Martin-Lof, Levin all worked in this area) is that one can never prove
> a given sequence or string is "random."

I believe this is overstating the case.  The only theorem along these
lines that I saw in Li and Vitanyi's book was that, for any logical
theory, there are at most a FINITE number of strings that can be proven
random.  The upper bound on the number of strings that can be proven
random is quite large, by the way -- it's larger than 2^n, where
n is the minimum number of bits needed to represent the logical theory.
Thus, although no algorithm can tell you, for all strings x, whether or
not x is random, it may be possible to prove a few particular strings
random (with respect to a given encoding of algorithms).

-----------------------------------------------------------------------------
Kevin S. Van Horn     | It is the means that determine the ends.
kevin@bert.cs.byu.edu |