Measuring static complexity (Q1186345)

Summary: The concept of `` pattern'' is introduced, formally defined, and used to analyse various measures of the complexity of finite binary sequences and other objects. The standard Kolmogorov-Chaitin-Solomonoff complexity measure is considered, along with Bennett's `logical depth', Koppel's 'sophistication', and Chaitin's analysis of the complexity of geometric objects. The pattern-theoretic point of view illuminates the shortcomings of these measures and leads to specific improvements. It gives rise to two novel mathematical concepts --- ``orders'' of complexity and ``levels'' of pattern, and it yields a new measure of complexity, the ``structural complexity'', which measures the total amount of structure an entity possesses.