3 ms·
Praptak: >Only assuming he'd be able to generate one. Is there a known algorithm for generating a provably Kolmogorov-uncompressible strings? In the theoretica
by im3w1l 14y ago
Praptak:
>Only assuming he'd be able to generate one. Is there a known algorithm for generating a provably Kolmogorov-uncompressible strings?
In the theoretical case he has almost a 255/256 of doing it he generates a string in a truly random fashion.
In the practical case his odds are much better. Many potential programs will a) refuse to run and b) give the same output.
- praptak 14y ago> In the theoretical case he has almost a 255/256 of doing it he generates a string in a truly random fashion. An interesting result. Do you have a link to the proof?
- Dylan16807 14y agoProof: There are k strings of bytelength n. There are k * 256 strings of bytelength n+1. k input strings can decompress to at most k output strings Therefore only k / (k * 256) of length n+1 strings can be compressed by a byte. The reason for 'almost' is the miniscule number of strings that will compress more than one bye.
- praptak 14y agoAh right, I totally missed the fact that compression by 1 bit doesn't beat the challenge!