Hacker News Reader

You always include the measurement of things needed to run the program too.

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" :)

View on HN

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.

Reply on news.ycombinator.com