On Tuesday, January 8, 2002, at 07:12 PM, F. Marc de Piolenc wrote:
I think they may be referring to a random string of _ASCII characters_. That would be subject to compression because it is not random at the bit level.
But 100:1? I have no idea how to achieve that.
The entropy of ordinary written English is about 2.2 bits per character. (Meaning, of course, that each new character contributes not much "surprise," i.e., is somewhat predictable. Entropies of various sources can be experimentally measured.) Others, particularly Eric Cordian, have already written at length on this claim of "100:1 compression of any file." Steve Smale at Berkeley is a famous and respected mathematician. He may be unaware of these claims, he may be senile, he may have worked on some small (no pun intended) aspect as a paid consultant, or the actual compression may be lossy and oriented toward replacing JPEG with a better lossy algorith (as Iterated Systems, IIRC, has been doing with fractal compression). The pigeonhole principle is not just a "theory," it's the _law_. You can't stuff distinct 64 things into 32 boxes without a lot of them being put into the same box. Which means reversing (decompressing) to the original won't work. The Chaitin-Kolmogorov view of algorithmic information theory is the best model we have. By the way, for all of you who struggled to understand Godel's Theorem expressed in the "logic" formulation that Godel first used--and that was the basis of Newman's fairly popular exposition--there are very understandable formulations of Godel's Theorem in terms of information theory and compressibility. Chaitin has a very clean one (no Kleene pun intended). Rudy Rucker does a good job of explaining it in "Mind Tools." Chaitin also has some good books and articles, though some of them jump too quickly into stuff like computing Omega...his "Scientific American"-level articles on the foundations of mathematics are better places to start...included in some of his books. --Tim May "A democracy cannot exist as a permanent form of government. It can only exist until the voters discover that they can vote themselves money from the Public Treasury. From that moment on, the majority always votes for the candidate promising the most benefits from the Public Treasury with the result that a democracy always collapses over loose fiscal policy always followed by dictatorship." --Alexander Fraser Tyler