Hacker News Reader

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...

View on HN

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.

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).

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

Reply on news.ycombinator.com