Wikipedia gives this definition for algorithmic randomness in terms of Kolmogorov complexity:
"Given a natural number c and a sequence w, we say that w is c-incompressible if $K(w) \geq |w|-c$. An infinite sequence S is Martin-Löf random if and only if there is a constant c such that all of S's finite prefixes are c-incompressible."
One really intuitive definition would be that random infinite binary strings are those that can't be computed by any finite program, ie. they have infinite Kolmogorov complexity.
Can someone tell me what is wrong with this? Why is wikipedia's definition better than my naive one?
Kolmogorov complexity only applies to finite strings (which is why the word "prefix" is in the definition you quoted) so being an infinite binary string not computable by any finite program does not make that string have infinite Kolmogorov complexity; that notion is meaningless for an infinite string. It would make that string merely "non-computable", which is much weaker than what one (usually) means when one says "random".
For example, an infinite binary string could be non-computable, yet have 0s at all its even bits. Such a string would hardly be random since "random" is meant to (somewhat) capture the result of flipping a coin infinitely often. Of course if one flipped a coin infinitely often, the result would not be heads every other time. Agreed?