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 |