alt Hacker NewsLately 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.
Replies
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.
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.