[tristenharr]

Lately I’ve felt Kolmogorov complexity is an unfair measurement because it takes for granted your underlying programming language as treats it as zero cost. In theory you could create a custom language and embed the program as data and “compress” a large random sequence with a better Kolmogorov complexity for that specific language than Pi, simply by not exposing the ability in the language to even work with Pi. I think what’s maybe more interesting is when you take into account the work of Dr. Futamura and the idea of Jones Optimality and view things through that lens.

[zzless]

His definition of Kolmogorov complexity is a bit loose. The rigorous definition uses Turing machines (or Minsky, or Post, or some sort of lambda expression, etc.) so the size is something specific. Different versions of complexity defined this way may give different values but have the same properties and asymptotics so one might just as well stick with the Turing kind. Chaitin's theorem (about the limit of Kolmogorov's complexity being just entropy) holds for all versions as well.

[adgjlsfhk1]

it's not just that they have the same asymptomatic. once you do the radix conversion (e.g. base 10 has log(10)/log(2) times more symbols), any 2 definitions are only off from each other by a constant

[AnotherGoodName]

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

[pcael]

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.

[pcael]

Does that solve the issue? You can always ask yourself if you can embedd something smaller or not? Kolmogorov is just comparing things.. plus, in order to specifically point to pi in the languages internal table, you will need complexity as large as your representation of pi.