Hacker News Reader

Comment by grandrew | Hacker News Reader

I have a question about how Kolmogorov complexity is related to "Human complexity" or complexity of understanding?

E.g. a program may be very complex in Kolmogorov terms, like describing 1000 random numbers - easy to understand: you have a database of numbers, and a simple procedure that would scan through it. You can also imagine some real-world microservices-based program with a good architecture and a lot of code that handles all the exception cases of incoming data, all easily understandable.

And now imagine an optimizing compiler for prolog programs. It may have much less code but the algorithm will be so complex that it might be impossible to fully understand its behaviour. E.g. fast-downward is a great example of such a program.

So I'm wondering what does Kolmogorov complexity actually tell? Or does it tell anything useful in "real"-world?

View on HN

Well, that's altering the 'language' that you're measuring the KC against. For instance, in the language that CS majors use the phrase "Kolmogorov Complexity" is sufficient to encode the concept of KC itself. And in the context of that language plus the concept of KC and adding in this entire thread, the letters KC themselves encode Kolmogorov Complexity in entirety.

So the 'real world' version isn't so easy to tell in absolute terms like that because the languages can differ. But if you were thinking of it like a compressor/decompressor pair, then moving things into the language is like moving things into the compressor/decompressor.

Naturally then you conclude that the "human complexity" depends greatly on the humans since any pair of humans creates a new universal description language that we can see as some base language plus the jargon that they are both familiar with.

> in the language that CS majors use the phrase "Kolmogorov Complexity" is sufficient to encode the concept of KC itself

Wait, isn't that just conflating "language" with "knowledge"/"information"? The underlying assumption here is that the CS major has an association of a concept encoded by the letters "Kolmogorov Complexity".

This is not universal, though, i.e. there's no computation that could derive the meaning behind these letters from the encoding alone. It's like claiming "620" is sufficient to encode Mozart's "Die Zauberflöte" ("The Magic Flute"), because in the language of a musician, the Köchel catalogue number along with the context would enable them to decode the full meaning.

But in reality you would still have to look up the number and the score somewhere so it's not really an encoding but more of a pointer or index. I'd see any technical term that way, in that the term itself is not an encoding, but a key/index/identifier of a concept, not a full definition of the concept itself.

What is easy or useful for one person to understand is often much less so for another.

Reply on news.ycombinator.com