At 2:07 PM 4/16/96, Perry E. Metzger wrote:
Timothy C. May writes:
Well, I don't view any of the "simple definitions" of randomness as especially useful; that is, the simple definitions have a kind of circularity (implicit in the points we both make). For example, "an object is "random" if it has no shorter description than itself," the classic Solomonoff-Kolmogorov-Chaitin definition, is quite elegant, but doesn't help much in many cases.
Except that it goes against our normal definitions of random in a crypto context. A string that is compressable might still be random. There is no reason you can't have a string of 20 1 bits in a row in a perfectly random sequence, for example. Usually, random sequences are non-compressable, but it is possible (though very improbable) for Hamlet to appear out of a random number generator, and it is of course quite compressable...
Sure, compressibility is not a determinant of randomness....nothing is, actually. This is my point about there being no simple definition of randomness. However, "most" objects derived from a "random-like process" have no shorter description than themselves, by a variant of the pigeonhole principle (i.e., there are more things of some size than descriptions of less than that size, so most "random" objects, are, perforce, not describable in short descriptions). --Tim May Boycott "Big Brother Inside" software! We got computers, we're tapping phone lines, we know that that ain't allowed. ---------:---------:---------:---------:---------:---------:---------:---- Timothy C. May | Crypto Anarchy: encryption, digital money, tcmay@got.net 408-728-0152 | anonymous networks, digital pseudonyms, zero W.A.S.T.E.: Corralitos, CA | knowledge, reputations, information markets, Higher Power: 2^756839 - 1 | black markets, collapse of governments. "National borders aren't even speed bumps on the information superhighway."