Whew, lots of good feedback here. Clearly I should have checked back earlier; I didn't realize there would be so much discussion. Excellent! Points addressed in

Whew, lots of good feedback here. Clearly I should have checked back earlier; I didn't realize there would be so much discussion. Excellent! Points addressed inline. > First of all, Kolmogorov complexity talks about the output from programs at a "higher-level". For example, to define the Kolmogorov complexity of plain text, we must talk about programs which output text. To define Kolmogorov complexity of, say, Ruby code, we must talk about programs which output Ruby code. And so on. The author mixes up the complexity of the text (eg. in the 3 line example) with the complexity of the code. These are two different things: the complexity of the text depends on the shortest program which outputs that text; the complexity of the code depends on the shortest program which outputs that code. Unequivocally true, and probably illustrative of the primary reason my article failed to express my intent, which was to illustrate Kolmogorov complexity as a useful measurement in reconciling the complexity of an algorithm (as expressed, say, in some natural spoken language, like English) with the complexity of its implementation: or, more precisely, how uniformly symmetrical some implementation which models an algorithm is to the algorithm itself. Perhaps it was too great of a leap to name Kolmogorov complexity as the conduit for this, but it seemed much closer than other similar textual comparison mechanisms (like, say, Hamming distance, which has its own interesting, but completely different, implications in comparing source code revisions). For example, in a language that supports pattern matching in function definitions, you could, in theory, implement a 2-arity addition function by defining all permutations of two 32-bit signed integers. This is, of course, an incredibly unhelpful implementation, not only in general comprehension and understanding (who's going to memorize the outputs of 2^64 function definitions?) but also in deriving the intent of the solution (in this case, the rules of addition). I find too often our implementations tend to focus on varieties of knowing "2 plus 2 equals 4", rather than understanding the nature of the solution, and was trying to use Kolmogorov complexity as a heuristic for identifying the relative complexity of two implementations to discover the one that is more general and correct. Perhaps that was too much of a leap. > Secondly, writing different programs with the same output doesn't change the Kolmogorov complexity; it merely improves an approximation (since Kolmogorov complexity is undecidable, we must approximate it). The author also uses the word "count" when talking about these approximate numbers, which I think is better than calling them "complexity". Again, this is absolutely true, although given that complexity is undecidable, it seemed convenient to synonymize "complexity" with "approximate complexity". Given this feedback, however, perhaps I'll update the article to attempt to clarify this distinction (possibly using "count" more, as that seems to have struck accord). > 1) When comparing different languages, like Ruby and Python, it might be nice to point out that the complexity can only change by a constant amount. This is because, in the worst possible scenario, we can write an interpreter for the other language. For example, if we use Python as our meta-language, we can denote the complexity of some text T as P(T); if we switch to using Ruby instead, the complexity R(T) <= P(T) + I, where I is the complexity of a Python interpreter written in Ruby. Since I doesn't depend on T, it is a constant, and therefore the choice of language becomes less important as the complexity of T increases. Great point! I'd also add that it's useful to understand the magnitude of I between languages, as that could (and should) be a contributing factor when choosing the language most appropriate for the problem. 2) Using Kolmogorov complexity as a benchmark doesn't seem like a great idea to me. [...] It can certainly be taken too far! I tried to caveat the article at the end, illustrating some of the pitfalls of making it the One True Metric, e.g. introducing artificial abstractions. Of course, this can extend to incidental language idiosyncrasies that can be exploited to shorten implementations. I was attempting to bring focus to subjective clarity as the final ruling metric, using Kolmogorov as assistance on the journey. > Just look at http://codegolf.stackexchange.com http://codegolf.stackexchange.com for example ;) I actually referenced code golf in the footnotes as a correlative example of refactorings based solely on Kolmogorov complexity. It's a double edged sword: some of my most profound "aha!" moments came from code golf exercises, although the vast majority of the time I just end up frowning at the non-obvious nature of the final winning submissions. Hopefully my responses are more clear than the article was, although I fear they perhaps were not. Thanks for the very thoughtful and measured feedback!