endless compression

[ed at eh3.com (Ed Hill)]

On Fri, 2004-08-13 at 10:07, Seth Gordon wrote:
> markw at mohawksoft.com wrote:
> > 
> > Not the point, if you have a repeatable compressor, then compression ratio
> > is largely unimportant. If you can compress something 3% over and over
> > again, then you can make it really small.
> 
> Yes, and if you have a perpetual motion machine, then Middle Eastern oil 
> reserves are largely unimportant.
> 
> Assume that you have a "repeatable compressor" that will losslessly 
> shrink any string of bits by 3% every time it is run.  What happens when 
> it receives a 100-bit input?  There are 2^100 possible inputs, but only 
> 2^97 possible outputs.  Therefore, there must be *some* inputs for which 
> this compressor cannot produce a 97-bit output--indeed, there must be 
> some inputs for which this compressor cannot produce a 99-bit output. 
> Therefore, this repeatable compressor cannot exist.  QED.


Seth is on-target.  The above is stated with much greater rigor at:

  http://www.faqs.org/faqs/compression-faq/part1/  [Section 9.1]

Apparently, cranks have been flirting this topic for some time and just
can't seem to let it go.  I wish this group would let it go.

Please?

Ed

-- 
Edward H. Hill III, PhD
office:  MIT Dept. of EAPS;  Rm 54-1424;  77 Massachusetts Ave.
             Cambridge, MA 02139-4307
emails:  eh3 at mit.edu                ed at eh3.com
URLs:    http://web.mit.edu/eh3/    http://eh3.com/
phone:   617-253-0098
fax:     617-253-4464