Re:Connections in Math: the two kinds of random
by pcael on Tuesday July 07, 2026 @08:16AM
(#48816686)
Of course you can. Kolmogorov complexity never says anything about finding lower bounds for specific elements. The lower bound is a statament about one string. The upper bound is statement about infinite strings, so you need to prove for infinite strings. In that sense you cant compress all strings and pointing a specific one without representing the index to it with a complexity a least as large as the string itself it represents. Read the part of pointing and telling things apart.
It's a bit like how benchmarks of compression utilities should always include the size of the utility itself. Otherwise someone can just submit a program with a dictionary of 256 common benchmark files for compression and claim "it compresses them to a single byte" :)