On Wednesday, January 9, 2002, at 02:39 PM, Tim May wrote:
You are missing the big picture. About 1 / 1^(N-1) bit strings of length N will have descriptions shorter than the bit string.
A typo. "1 / 2^(N-1)" is what I meant to type. If N = 100, about 1/2^99 of the bit strings have "short" (catchy, memorable, loosely speaking) descriptions. Most of the rest actually take more bits to describe if described in terms of "words" (small patterns, runs). This is what we mean when we say they are their own shortest descriptions. This is similar, by the way, to poker or bridge hands. In a fair deal, all hands are equally likely. However, because of our naming conventions and interest in "all hearts" or "a sequential run of spades from 10 to Ace," we are fooled into thinking some of these hands are "rarer" than "random hands." Again, this is just one facet of a very interesting topic. --Tim May