6 ms·

Can you elaborate on Kolmogorov complexity and its relevance to someone who has not encountered the term before? (I have wikied it: http://en.wikipedia.org/wiki

Can you elaborate on Kolmogorov complexity and its relevance to someone who has not encountered the term before? (I have wikied it: http://en.wikipedia.org/wiki/Kolmogorov_complexity http://en.wikipedia.org/wiki/Kolmogorov_complexity but sleep deprivation may be hindering my ability to spot the link)

tel 17y ago
Kolmogorov Complexity relates to the idea that you can use some kind of computer to encapsulate repeating patterns. When you do this, you have to store the data of your program somewhere and its size relates (sort of) to abstractly just how complex the problem was. It's also equivalent to Minimum Message Length, so looking into that might help. Roughly, the relevance remains the same if you just remove "Kolmogorov" from the op's statement. The manager doesn't understand that inventing a whole new solution is complex no matter how many or few people use it. Which isn't strictly true, but it's definitely a good rule of thumb.
gjm11 17y ago
To someone who doesn't understand what's going on, it may seem simpler to make something work for one person than to make it work for lots of people; but in fact the version that works for lots of people may be no less simple. (It may even be simpler, if it's necessary to put in special-case testing to make sure that only one person can use it.) From an implementer's perspective, the right measure of the complexity of a system is "how much code does it take to implement?" (which is more or less Kolmogorov complexity) rather than "how many things can it do?" or "how wide is its range of possible behaviours?". A few other remarks on Kolmogorov complexity: 1. "Random" is often best understood as "of high Kolmogorov complexity": a sequence of numbers is random if there's no way to generate it that really saves anything over listing all the numbers; no pattern that makes it predictable. (In practice, what you usually care about is that certain restricted kinds of pattern don't occur, which is kinda like a version of Kolmogorov complexity where you're limited to using programs in a language that isn't Turing-complete.) 2. If you apply Ockham's razor in the form "prefer hypotheses with lower Kolmogorov complexity" together with Bayes' theorem, you get something that in a certain (rather artificial) sense is as effective a problem solver as anything mechanized can be. Unfortunately it's unimplementable in practice, because ... 3. It's more or less always impossible to determine for sure what the Kolmogorov complexity of anything is. (Because to be able to do that you'd need to be able to answer the question "do these two programs do the same thing or not?", and that's equivalent to the halting problem.) 4. (This is controversial, but it's my opinion and that of at least some other contributors here.) When assessing (e.g.) scientific hypotheses for "simplicity" or "parsimony", something like Kolmogorov complexity is the Right Way to understand (un)simplicity; failure to appreciate this is, e.g., what makes some people dislike the "many worlds" interpretation of quantum mechanics on the grounds of extravagance, or think that "God did it" is a useful explanation for otherwise-surprising features of the universe.
- orangecat 17y ago
  If you apply Ockham's razor in the form "prefer hypotheses with lower Kolmogorov complexity" together with Bayes' theorem, you get something that in a certain (rather artificial) sense is as effective a problem solver as anything mechanized can be. Unfortunately it's unimplementable in practice, because ... Coming across AIXI was what got me interested in algorithmic information theory. It is indeed useless in it's "pure" form, but there's a variation using Monte Carlo search that apparently does pretty well: http://arxiv.org/abs/0909.0801 http://arxiv.org/abs/0909.0801 (This is controversial, but it's my opinion and that of at least some other contributors here.) When assessing (e.g.) scientific hypotheses for "simplicity" or "parsimony", something like Kolmogorov complexity is the Right Way to understand (un)simplicity; failure to appreciate this is, e.g., what makes some people dislike the "many worlds" interpretation of quantum mechanics on the grounds of extravagance, or think that "God did it" is a useful explanation for otherwise-surprising features of the universe. Yes. In fact after reading the Less Wrong quantum physics sequence (http://lesswrong.com/lw/r5/the_quantum_physics_sequence/ http://lesswrong.com/lw/r5/the_quantum_physics_sequence/), I find that "the wavefunction collapsed" and "God did it" are remarkably similar statements.
- nostrademons 17y ago
  3. It's quite possible to determine what the Kolmogorov complexity of something is, it's only impossible to determine what the Kolmogorov complexity of everything is. The halting problem only states that it's impossible to prove whether an arbitrary Turing machine halts. There're many Turing machines that can be proved to halt, some quite easily. For example, int main(int argc, char** argv) { return 1; } can be proved to halt pretty easily, just looking at the CFG for the program.
  - Herring 17y ago
    Yeah CS theory & practice are often quite different. http://en.wikipedia.org/wiki/Termination_analysis http://en.wikipedia.org/wiki/Termination_analysis
  - gjm11 17y ago
    I think that even in practice being able to determine the Kolmogorov complexity exactly is very decidedly not the usual case; you need to know that every program shorter than your candidate fails to do the right thing. Your general point is very much correct, though. A clearer-cut application: In general, one cannot prove that a program does what it's supposed to; but if doing that is important, "all" you have to do is write it in a way that makes a correctness proof possible.
inerte 17y ago
In other words, what orangecat meant is that adding more code, even "simple" code, adds complexity to a software project. Adding 50 easy features is equal to adding one heck of complex feature made of 50 sub parts. The link with Kolmogorov is, I believe, that each piece added moves the set away from being simpler. First time I read about Kolmogorov, hopefully I got it right. Anyway my first paragraph is true!
- orangecat 17y ago
  Essentially correct. Kolmogorov complexity is the amount of information it takes to fully describe something. A million random bits have high complexity because the shortest way to describe them is to literally list them all. The first million bits of pi have low complexity because they can be generated by an algorithm that takes much less than a million bits to describe. (The algorithm may take a long time to run, but Kolmogorov complexity doesn't care about that). From that perspective implementing a new login process for "just one client" is worse than changing it for everyone, because it increases the size of the program's description. The revised software must describe the existing login process, the new process, and the logic for deciding which clients use which process. Whereas changing it for everyone requires only describing the new process, and allows you to eliminate the description of the previous process.
mquander 17y ago
I think the grandparent meant cyclomatic complexity rather than Kolmogorov complexity. Special-casing a change for one person means at least one more execution branch.

tel 17y ago

Kolmogorov Complexity relates to the idea that you can use some kind of computer to encapsulate repeating patterns. When you do this, you have to store the data of your program somewhere and its size relates (sort of) to abstractly just how complex the problem was. It's also equivalent to Minimum Message Length, so looking into that might help. Roughly, the relevance remains the same if you just remove "Kolmogorov" from the op's statement. The manager doesn't understand that inventing a whole new solution is complex no matter how many or few people use it. Which isn't strictly true, but it's definitely a good rule of thumb.

gjm11 17y ago

To someone who doesn't understand what's going on, it may seem simpler to make something work for one person than to make it work for lots of people; but in fact the version that works for lots of people may be no less simple. (It may even be simpler, if it's necessary to put in special-case testing to make sure that only one person can use it.) From an implementer's perspective, the right measure of the complexity of a system is "how much code does it take to implement?" (which is more or less Kolmogorov complexity) rather than "how many things can it do?" or "how wide is its range of possible behaviours?". A few other remarks on Kolmogorov complexity: 1. "Random" is often best understood as "of high Kolmogorov complexity": a sequence of numbers is random if there's no way to generate it that really saves anything over listing all the numbers; no pattern that makes it predictable. (In practice, what you usually care about is that certain restricted kinds of pattern don't occur, which is kinda like a version of Kolmogorov complexity where you're limited to using programs in a language that isn't Turing-complete.) 2. If you apply Ockham's razor in the form "prefer hypotheses with lower Kolmogorov complexity" together with Bayes' theorem, you get something that in a certain (rather artificial) sense is as effective a problem solver as anything mechanized can be. Unfortunately it's unimplementable in practice, because ... 3. It's more or less always impossible to determine for sure what the Kolmogorov complexity of anything is. (Because to be able to do that you'd need to be able to answer the question "do these two programs do the same thing or not?", and that's equivalent to the halting problem.) 4. (This is controversial, but it's my opinion and that of at least some other contributors here.) When assessing (e.g.) scientific hypotheses for "simplicity" or "parsimony", something like Kolmogorov complexity is the Right Way to understand (un)simplicity; failure to appreciate this is, e.g., what makes some people dislike the "many worlds" interpretation of quantum mechanics on the grounds of extravagance, or think that "God did it" is a useful explanation for otherwise-surprising features of the universe.

orangecat 17y ago
If you apply Ockham's razor in the form "prefer hypotheses with lower Kolmogorov complexity" together with Bayes' theorem, you get something that in a certain (rather artificial) sense is as effective a problem solver as anything mechanized can be. Unfortunately it's unimplementable in practice, because ... Coming across AIXI was what got me interested in algorithmic information theory. It is indeed useless in it's "pure" form, but there's a variation using Monte Carlo search that apparently does pretty well: http://arxiv.org/abs/0909.0801 http://arxiv.org/abs/0909.0801 (This is controversial, but it's my opinion and that of at least some other contributors here.) When assessing (e.g.) scientific hypotheses for "simplicity" or "parsimony", something like Kolmogorov complexity is the Right Way to understand (un)simplicity; failure to appreciate this is, e.g., what makes some people dislike the "many worlds" interpretation of quantum mechanics on the grounds of extravagance, or think that "God did it" is a useful explanation for otherwise-surprising features of the universe. Yes. In fact after reading the Less Wrong quantum physics sequence (http://lesswrong.com/lw/r5/the_quantum_physics_sequence/ http://lesswrong.com/lw/r5/the_quantum_physics_sequence/), I find that "the wavefunction collapsed" and "God did it" are remarkably similar statements.
nostrademons 17y ago
3. It's quite possible to determine what the Kolmogorov complexity of something is, it's only impossible to determine what the Kolmogorov complexity of everything is. The halting problem only states that it's impossible to prove whether an arbitrary Turing machine halts. There're many Turing machines that can be proved to halt, some quite easily. For example, int main(int argc, char** argv) { return 1; } can be proved to halt pretty easily, just looking at the CFG for the program.
- Herring 17y ago
  Yeah CS theory & practice are often quite different. http://en.wikipedia.org/wiki/Termination_analysis http://en.wikipedia.org/wiki/Termination_analysis
- gjm11 17y ago
  I think that even in practice being able to determine the Kolmogorov complexity exactly is very decidedly not the usual case; you need to know that every program shorter than your candidate fails to do the right thing. Your general point is very much correct, though. A clearer-cut application: In general, one cannot prove that a program does what it's supposed to; but if doing that is important, "all" you have to do is write it in a way that makes a correctness proof possible.

inerte 17y ago

In other words, what orangecat meant is that adding more code, even "simple" code, adds complexity to a software project. Adding 50 easy features is equal to adding one heck of complex feature made of 50 sub parts. The link with Kolmogorov is, I believe, that each piece added moves the set away from being simpler. First time I read about Kolmogorov, hopefully I got it right. Anyway my first paragraph is true!

orangecat 17y ago
Essentially correct. Kolmogorov complexity is the amount of information it takes to fully describe something. A million random bits have high complexity because the shortest way to describe them is to literally list them all. The first million bits of pi have low complexity because they can be generated by an algorithm that takes much less than a million bits to describe. (The algorithm may take a long time to run, but Kolmogorov complexity doesn't care about that). From that perspective implementing a new login process for "just one client" is worse than changing it for everyone, because it increases the size of the program's description. The revised software must describe the existing login process, the new process, and the logic for deciding which clients use which process. Whereas changing it for everyone requires only describing the new process, and allows you to eliminate the description of the previous process.

mquander 17y ago

I think the grandparent meant cyclomatic complexity rather than Kolmogorov complexity. Special-casing a change for one person means at least one more execution branch.