3 ms·
Can't he just send you a Kolmogorov-random file? The definition of randomness (in Kolmogorov sense) basically corresponds directly to his challenge. Also, Kol
by skatenerd 12y ago
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#Kolmogorov_randomness http://en.wikipedia.org/wiki/Kolmogorov_complexity#Kolmogoro...
- mappu 12y agoHow 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).
- skatenerd 12y agoI 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
- darkmighty 12y agoRead 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.