4 Some concepts related to complexity

4.3 Minimum description size

One of the most interesting of the serious definitions of complexity is that of the minimum possible length of a description in some language, also called Kolmogorov *1 complexity*2. The language is frequently taken to be that of a Turing machine. Thus if a description can be greatly compressed without loss, then this is counted as simpler than one that cannot. By this definition highly ordered expressions come out as simple and random expressions as maximally complex.

This measure has more to do with the amount of information in an expression than its complexity. For example it has been shown [5] that you can not prove that expressions are (much) more complex than the original axioms in a formal system, despite the fact that there is no intuitive limit to the complexity of possible theorems in the system. This reading is confirmed by the close connection of this with other (entropic) measures of information like Shannon's [31]. Expressions with little information will be limited in their complexity, but that is not to say that all expressions with a high information content are complex; one can surely imagine a situation in which you are given a lot of information, but where most of it is unrelated, so that the whole is incompressible and large but ultimately simple. In fact the more interrelations there are, the more compressible the expression is likely to be, but this would also tend to make it more rather than less complex.

What is Complexity? - The philosophy of complexity per se with application to some examples in evolution - 14 JUN 95

[Next] [Previous] [Up] [Top] [Contents]

Generated with CERN WebMaker