3 ms·
Very relevant: https://en.wikipedia.org/wiki/Kolmogorov_complexity#Incomputability_of_Kolmogorov_complexity https://en.wikipedia.org/wiki/Kolmogorov_complexity#
by im3w1l 14y ago
Very relevant:
https://en.wikipedia.org/wiki/Kolmogorov_complexity#Incomputability_of_Kolmogorov_complexity https://en.wikipedia.org/wiki/Kolmogorov_complexity#Incomput...
- DanBC 14y ago> By definition, the Kolmogorov complexity K of a string x is defined as the length of the shortest program (self-extracting archive) computing x. K(x) itself cannot be computed, only approximated from above, namely by finding better and better compressions, but even if we reach K(x) will never know whether we have done so. For a text string like enwik8, Shannon's estimate suggests that enwik8 should be compressible down to 12MB. The current record is 15,949,688 bytes.