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.
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.