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.
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
(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/), I find that "the wavefunction collapsed" and "God did it" are remarkably similar statements.
int main(int argc, char** argv) {
return 1;
}
can be proved to halt pretty easily, just looking at the CFG for the program.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.
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!
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.
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.
That's probably the most frustrating thing I hear from non-technical people, because they really think they're making it easier. Sadly Kolmogorov complexity is not yet a required course in schools.