The thing is that any computable complexity measure allows one to algorithmically produce an infinite which seems to have a complexity which goes to infinite as it get longer but since it is the product of a finite length computer program has finite complexity.<p>On the other hand, you can prove that for &quot;nearly all&quot; finite sequences of symbols, the algorithmic complexity is within a constant of naive statistical measures.