3 ms·
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 fac
by 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 agoIf 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 ago3. 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 agoYeah CS theory & practice are often quite different. http://en.wikipedia.org/wiki/Termination_analysis http://en.wikipedia.org/wiki/Termination_analysis
- gjm11 17y agoI 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.