Eric Cordian wrote:

Declan opines:

...

I'm naturally skeptical of this claim (until I can verify it for myself), but I do not believe the claim is "we can encode random data at 100:1."

...

From the article:

"ZeoSync said its scientific team had succeeded on a small scale in compressing random information sequences in such a way as to allow the same data to be compressed more than 100 times over -- with no data loss."

Now of course it's possible they were horribly misquoted. Still, it is worrisome that so many people quoted in the article think such algorithmic gymnastics are mathematically possible.

The overpowering stench of snake oil pervades the ether I particularly liked: "The techniques described by ZeoSync would mark a break with the dozens of existing compression technologies, including MPEG for video and music and JPEG for pictures and graphics are able to compact data at compression rates up to 10 times the original. These algorithms typically work by eliminating long strings of identifiable bits of data such as blue sky, green grass or the white background of a snow-covered landscape." Which sounds like someone who doesn't know what they are talking about being misreported by someone who doesn't understand (*) "ZeoSync said its scientific team had succeeded on a small scale" "The company's claims, which are yet to be demonstrated in any public forum" "ZeoSync, whose Web site can be located at http://www.zeosync.com/" "Among the scientific team working with ZeoSync is Steve Smale, one of America's most renowned mathematicians. Smale is an emeritus professor at the University of California at Berkeley and the 1966 winner of the Fields Prize, the Nobel Prize for researchers in this field. He could not be reached for comment on his role in the project." I bet. Ken Brown (*) clue for those who have too much of a life to bother with things like file structures and encoding (though why would they be reading cypherpunks?) - JPEG is a lossy compression method that tries to recode "real world" pictures in a way that *looks* almost as good as the real thing but takes up less space, by smoothing out gradual changes of colour (and other stuff as well). It doesn't "typically work by eliminating long strings of identifiable bits of data". And it doesn't compress "up to 10 times", it compresses as much as you like, with a trade-off between file size and image quality. MPEG, AFAIK, is similar.

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

From: <georgemw@speakeasy.net>

Maybe I'm oversimplifying, but it seems to me that Godel's theorem follows trivilaly once you've heard of Cantor's diagonal slash. As I understand it, Godel's theorem says in essence that in any system complex enough to include the irrational numbers there must be statements which are true in that system but which cannot be proven in that sytem. But since there are uncountably many irrational numbers, there are uncountably many statements of the form A=A which are true but which cannot be expressed with a finite number of symbols.

I think you're oversimplifying. The theorem doesn't say "there are statements which can't be written", but "there are statements (implicitly writeable) which can't be proven". Mark

On Tue, 8 Jan 2002, Steve Schear wrote:

combinations/permutations and auto correlations to code for the runs. I say attempted, because I was never able to find acceptable algorithms to satisfy my requirement. I still believe these algorithms exist, it was just my limitations in identifying the underlying math needed.

http://www.google.com/search?q=IFS+image+compression&sourceid=opera&num=100&ie=utf-8&oe=utf-8