Re:The $5000 Compression Challenge
by function_seven on Sunday March 08, 2015 @01:45AM
(#9164836)
> that you could fit the gunzip binary in the reduced space
What's funny is that Patrick (the challenger) asked if a bash script consisting solely of a call to gunzip would suffice as the decompressor. In other words, all he had to do was compress the file by more than the amount of the script. Mike allowed it, knowing that even a tiny "decompressor" that really just called out to the real thing, would still be larger than the compression achievable on a well-crafted random blob.
To be more formal, the challenger is finding what he believes to be a string that is Kolmogorov-random, and betting (quite safely) that the challenged party can't prove him wrong.
http://en.wikipedia.org/wiki/Kolmogorov_complexity#Kolmogoro...