Re: Random data cannot be compressed

In article <j881t3t1sfpsu837s4r8fnv52be1n9tms5@[EMAIL PROTECTED]
>,
 Steve Schafer <steve@[EMAIL PROTECTED]
> wrote:

> On Thu, 06 Mar 2008 17:48:34 -0800, Ron Garret <rNOSPAMon@[EMAIL PROTECTED]
>
> wrote:
> 
> >I finally got fed up with having to repeat myself all the time so I put

> >up a set of slides that explains all this:
> >
> >http://www.flownet.com/ron/halting_problem.pdf
> >
> >This is an old presentation, and some of these slides are not on point 
> >so you might want to skip ahead and start with slide 12.
> 
> Look, I have no vested interest in the (in)compressibility of random
> data. This whole discussion is nonsense about nonsense. I am well aware
> of the definitions of randomness and why random data cannot be
> compressed in general (and also why no compression algorithm can
> compress all data sets). The only reason that I got involved at all is
> because Richard is playing you, and probably laughing his head off while
> at it. I was merely trying to explain _how_ he was playing you, so that
> you'd have a way to fight back. But you just can't seem to understand
> that the whole thing is semantic legerdemain.
> 
> WHEREAS: You're completely missing the point. This isn't about
> compressing random data IN GENERAL. This is about compressing a SPECIFIC
> data set, which happens to have been created using a random process.

I get that.  What YOU don't get is that you have to count the length of 
the decompression algorithm.

> In the following, D is a constant that has exactly the same value as the
> "plain text" that we wish to compress. Given any plain text (randomly
> generated or not), we can obviously create a constant D that has that
> plain text as its value.
> 
> Here is the algorithm (pseudocode) to compress it to one bit:
> 
>  IF plainText = D THEN
>    return 1
>  ELSE
>    return 0
>  ENDIF
> 
> And here's the associated decompression algorithm:
> 
>  IF compressedData = 1 THEN
>    return D
>  ELSE
>    return ""
>  ENDIF

Why stop there?  You can compress D to zero bits.  As a bonus, the 
decompression algorithm is even shorter:

  return D

> Do you get it now? For every SPECIFIC data set, we create a new pair of
> SPECIFIC compression and decompression algorithms.

Sure.  But if D is random then the length of the decompression algorithm 
plus the data will be at least as long as D.

> Yes, it's meaningless.

No, it isn't.  It's actually quite an important fact of information 
theory.

rg