endless compression

[sethg at ropine.com (Seth Gordon)]

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.

(If nobody else is interested in this argument, I'll let Mark have the 
last word here.)

-- 
"Remember that "freedom" is not just a word. It is a squishy,
  concept-lite word which invokes positive feelings." --Fafblog
// seth gordon // sethg at ropine.com // http://dynamic.ropine.com/yo/ //