News for hackers. Stuff that matters.
Re:The $5000 Compression Challenge by skatenerd on Saturday March 07, 2015 @10:03PM (#9164315)
Can't he just send you a Kolmogorov-random file? The definition of randomness (in Kolmogorov sense) basically corresponds directly to his challenge.

Also, Kolmogorov-random sequences vastly outnumber non-random sequences in general, so with a long-enough file, I wonder how certain he can be that he has generated such a file.

http://en.wikipedia.org/wiki/Kolmogorov_complexity#Kolmogoro...

Re:The $5000 Compression Challenge by darkmighty on Saturday March 07, 2015 @11:36PM (#9164555)
Read the article, this is a circumvention rather than compression, although if you define Komogorov-randomness appropriately, such a definition would work.

But modern OS's have non-determinism available: take a Kolmogorov-random file of size n which can be generated by a program n+1. Then, replace a certain part of the program (totaling k bits, and delete 2 extra bits) with a function drawing k+2 random bits from the OS. Then with probability 2^-(k+2), you win.

Re:The $5000 Compression Challenge by mappu on Saturday March 07, 2015 @10:43PM (#9164417)
How do you determine whether the file is kolmogorov-random?

The only approach is to try a perfect kolmogorov compressor, which doesn't exist (well, excepting brute force over the space of possible turing machines).

Re:The $5000 Compression Challenge by skatenerd on Sunday March 08, 2015 @03:35AM (#9164928)
I bet that with longer strings, the odds of drawing a kolmogorov-random string are high enough that he's guaranteed to make money from his Challenge