There seems to be a misinterpretation of the point I was making about randomness and how no number (or sequence) can be _proved_ to be random.
This has some fascinating tie-ins to "cryptoregular" strings, which are strings which appear to be "regular" (a variant of randomness, meaning all digits are equally represented...high entropy) but which, with the right transformation, suddenly lose their regularity. ... Basic definition: A random string has no shorter description than itself. That is, it is incompressible. ...
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." As in some diabolically clever IQ test, an apparently random sequence may have some shorter description, or compression, that means it does not fit this definition of randomness.
The point here is for a number or sequence which is _given_, just presented, as in: "Is the sequence 100010001010110010101 random?" Or, "Is the number 9045886804 random?" Variants of this question come up all the time, as in predicting the next term of a sequence, trying to determine if a sequence of characters is likely to be just noise or is instead likely to be a message, and in issues of whether data is maximally compressed or can be compressed still further. These numbers are "found objects" in the sense that one generally has no idea what "model" or "theory" generated them. Someone looking at the first example, 100010001010110010101, might subject it to all kinds of tests: -visual inspection to see if it's some "obvious" number (such as "1010101010101010" would be, or "01011101110111" might be) -statistical tests, to see if it deviates "significantly" from the expected pattern of random numbers (regular distribution of digits, of pairs, triples, quadruples, etc.). The usual arsenal of entropy measurements, chi-square tests, null hypothesis testing, etc. -other tests to see if the number is related to other known numbers, which could be things like the day of the year, the digits of pi, the phone number of whoever generated the number, etc. -other tests and guesses that cryptanalysts and puzzle-solvers are familiar with A plausible result for someone to announce, after such a series of tests, is "I can't find any patterns, and the distribution of digits falls within expected ranges. We've compared the number against the suspect's various numbers and can find no linkages. It looks pretty random to us." (By "random" he essentially means "like the result of a sequence of coin tosses." Fair coin, of course.) But can he ever say "I can prove the number is random"? No. There's always some chance an even-cleverer puzzle solver will find the pattern, the key that unlocks the randomness. For example, most ciphertexts pass nearly all statistical tests for randomness, "look" random, and even _act_ like random numbers (recall the Blum-Blum-Shub pseudorandom number generator and how good it is). But simple application of the key turns the seemingly random "100010001010110010101" into "ATTACK." Let's look at the second example. Is the number "9045886804" random or not? And can we _prove_ it's random? (If you're worred that these numbers are somehow too small, don't worry. The same reasoning applies to any number or sequence one might encounter, including short numbers and multi-page numbers or sequences (such as PGP might generate)). The cryptanalyst or problem-solver looks for the patterns, the statistical distributions and entropies, and _any other_ links he can think of. That is, his "models" for the generator of this number are not known to him, but he may make some guesses based on the owner of the number, the score in the SuperBowl, the age of Bill Clinton, etc. That is, he'll look to see if the number is some sort of simple cipher or transpostion based on one of the "unrandom" numbers around him. To cut to the chase, can he ever "prove" the number is random? Can he even claim that the generator of the number "must have" used a process that is commonly used to generate numbers with a good approximation to a random process (flippin coins, alpha counts, etc.)? Suppose he declares to his boss, Admiral Inman, that he has "proved" the number is "random." Inman says to him: "This post was written by this trouble-maker Tim May, who even gives his phone number in every post he writes. What happens if we reverse the digits of his number? 408-688-5409 turns into 9045886804! Some "random" number! Clean out your desk tonight." Now is it kosher to take the "theory" of my phone number and allow it to be included in the analysis of wheter a number is random or not? Of course it is! In the real world, this is what we mean by randomness and predictabilty, whether we can find patterns and structure. And this is what cryptanalysts really do, and what good password-guessing programs do: they take account owner information such as name, spouse's name, pet's name, birthdate, and any other information they can scrounge about an account owner and then run permuations and hope for the best. Some percentage of the time, the passwords are "guessed," meaning that they were not very random at all. (This was the point I was making about famous numbers (like "729"), paradoxes (there are no "uninteresting" numbers, because the smallest "uninteresting" number is automatically interesting, and in fact is has a short description), and the number listed in Chaitin's book. I hope this explanation here makes it a bit clearer.) In this real world of trying to break cyphers, all is fair. All models may be considered, though not all models can be (e.g., one would not try applying the phone number of Chester Umbizi in Nairobi, Kenya at random!). No number can be proved to have no shorter description than itself. And as various shorter descriptions are found, with whatevr effort it takes, it cannot be proved that the description is the shortest that will ever be found. It may be strongly susepected that no shorter description exists. In fact, most numbers are incompressible, but a simple counting argument, in any theory. (For example, of the 100-binary-digits, not many of them have 50-digit compressions, and even fewer have 10-digit descriptions. Work out the numbers.) So, if someone tells you they've "proved" a particular number is random, just smile. --Tim May -- -- .......................................................................... Timothy C. May | Crypto Anarchy: encryption, digital money, tcmay@netcom.com | anonymous networks, digital pseudonyms, zero 408-688-5409 | knowledge, reputations, information markets, W.A.S.T.E.: Aptos, CA | black markets, collapse of governments. Higher Power:2**859433 | Public Key: PGP and MailSafe available.