Randomness and compressibility

I've just got myself into a discussion about Kolmogorov complexity. The other person was claiming that one can detect randomness in a binary sequence by calculating the compressibility of the sequence: if it can't be compressed enough, then it's random. I'm a bit sceptical about this, in part because I can't see how one can calculate the maximum amount of compressibility possible.

My intuition is that compressibility must implicitly force a definition on randomness, and hence imply an algorithm that generates this. But that algorithm must have fixed parameters, and if we make them random, we have something that is, in an informal sense, more random, but which would appear to be less random.

Does any of this make sense, and if I'm wrong, why?

Incidentally, the post that started it is here:
<http://www.pandasthumb.org/archives/2005/12/moving_the_goal.html#comment-64418>
It was part of nother discussion, so there's a lot of other stuff you'll have to wade through to follow this.

Bob

--
Bob O'Hara
Department of Mathematics and Statistics
P.O. Box 68 (Gustaf Hällströmin katu 2b)
FIN-00014 University of Helsinki
Finland

Telephone: +358-9-191 51479
Mobile: +358 50 599 0540
Fax:  +358-9-191 51400
WWW:  http://www.RNI.Helsinki.FI/~boh/
Journal of Negative Results - EEB: www.jnr-eeb.org
.

Relevant Pages
Loading