Randomness of a bit string

[kevin@axon.cs.byu.edu (Kevin Vanhorn)]

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 |