Random Data Compressed 100:1 (Guffaw)

[Tim May]

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